Complexity Zoo:W

From Complexity Zoo
Jump to navigation Jump to search

Back to the Main Zoo - Complexity Garden - Zoo Glossary - Zoo References

Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

Lists of related classes: Communication Complexity - Hierarchies - Nonuniform

W[1] - WAPP - WAPPcc - WHILE - W[P] - WPP - W[SAT] - W[*] - W[t] - W*[t]


W[1]: Weighted Analogue of NP

The class of decision problems of the form (x,k) (k a parameter), that are fixed-parameter reducible to the following:

    Weighted 3SAT: Given a 3SAT formula, does it have a satisfying assignment of Hamming weight k?

A fixed-parameter reduction is a Turing reduction that takes time at most f(k)p(|x|), where f is an arbitrary function and p is a polynomial. Also, if the input is (x,k), then all Weighted 3SAT instances the algorithm queries about must have the form <x',k'> where k' is at most k.

Contains FPT.

Defined in [DF99], where the following is also shown:

  • If FPT = W[1] then NP is contained in DTIME(2o(n)).

W[1] can be generalized to W[t].

WAPP: Weak Almost-Wide PP

The class of decision problems for which there exists a #P function f, a polynomial p, and an ε > 0, such that for all inputs x,

  1. If the answer is "yes" then 2p(|x|) ≥ f(x) > (1+ε) 2p(|x|)-1.
  2. If the answer is "no" then 0 ≤ f(x) < (1-ε) 2p(|x|)-1.

Defined in [BGM02], where it is also shown that WAPP is contained in AWPP and SBP.

WAPPcc: Communication Complexity WAPP

This class is parameterized by a constant ε. The corresponding model consists of randomized protocols such that yes-inputs are accepted with probability in [(1-ε)α,α] and no-inputs are accepted with probability in [0,α] where α is to be thought of as a function of n. The cost of a protocol is defined to be its communication cost plus log(1/α).

Does not admit efficient amplification with respect to the ε parameter [GLM+15].

The complexity measure associated with WAPPcc is equivalent to the so-called (one-sided) smooth rectangle bound and also to the approximate nonnegative rank of the communication matrix [KMSY14].

WHILE: While programs and some restrictions

While is a theorical programing language defined in [jon98], is a way to define syntacticaly P and a syntactic resctriction of WHILE is exactly L. The important point is that those two languages are powerful enough to simulate all of P (and L) and when we write a program in this language we never need to prove his time (space) complexity, since the language garantee it !

In While, input are composed only of lists (in a lisp-way where a list is either an empty list or a pair of his first element and his tail) and the elements of the list and variables are only pointers to list.

A program contains global variables and procedures.

  • Every procedure are composed of a name, a list of argument and local variables and a list of command. The procedure doesn't return any value, they only affect global variables.
  • The command are: variable affectation, while loop, if/then/else and procedure call.
  • The empty list is considered as false and everything else as true, this is the only way to do while/if test.

There are three primitives function, tail, head, and cons(h,t), who give the first value of a list, the tail of the list and who return a list whose first element is h and the rest of the list is t and we can call defined procedure.

We can then define WHILE/cons-rec which is WHILE without "cons" primitive and procedure call[#]. It is equivalent to L. The trick to do the computation in logspace is that without recursion we only need to save a fixed number of variables who are only pointers to part of the input, so they only take logspace. Since any logspace TM can avoid having a work tape by having a fixed number of reading head on his input, we can simulate logspace TM by using a variable for every reading head. (The binary string is coded as a list of () for 0 and (()) for 1, so equality can be checked trivially)

[#] in fact we only need to forbid recursive call, hence the name, but when we lose recursion we can assume there is no procedure call w.l.o.g, in fact in [jon98] WHILE is first defined without procedure call and procedure are defined later, but this presentation may be more easy to understand and at least more general.

We can then also define WHILErec/cons which is WHILE without "cons" primitive but with procedure calls, and hence recursion. It is equivalent to P. The trick to do a computation of a WHILErec/cons in P is to memoize the couple (global variables, input) when a procedure is called and the value of the globals variable when the procedure end, since we don't have cons, only a polynomial number of call will really be executed and we can detect loop. Simulating P in WHILErec/cons is quite more subtle, P TM are equivalent to some counter machine wich can easily be simulated by WHILE programs with cons, and then we can simulate the cons thanks to the call stack.

W[P]: Weighted Circuit Satisfiability

The class of decision problems of the form (x,k) (k a parameter), that are fixed-parameter reducible to the following problem, for some constant h:

    Weighted Circuit-SAT: Given a Boolean circuit C (with no restriction on depth), does C have a satisfying assignment of Hamming weight k?

See W[1] for the definition of fixed-parameter reducibility.

Defined in [DF99].

Contains W[SAT].

WPP: Wide PP

The class of decision problems solvable by an NP machine such that

  1. If the answer is "no," then the number of accepting computation paths exactly equals the number of rejecting paths.
  2. If the answer is "yes," then their difference exactly equals a function f(x) computable in polynomial time (i.e. FP).

Defined in [FFK94].

Contained in C=P ∩ coC=P, as well as AWPP.

Contains SPP and LWPP.

W[SAT]: Weighted Satisfiability

The class of decision problems of the form (x,k) (k a parameter), that are fixed-parameter reducible to the following problem, for some constant h:

    Weighted SAT: Given a Boolean formula F (with no restriction on depth), does F have a satisfying assignment of Hamming weight k?

See W[1] for the definition of fixed-parameter reducibility.

Defined in [DF99].

Contains W[t] for every t, and is contained in W[P].

W[*]: Union of W[t]'s

The union of W[t] over all t.

W[t]: Nondeterministic Fixed-Parameter Hierarchy

A generalization of W[1].

The class of decision problems of the form (x,k) (k a parameter), that are fixed-parameter reducible to the following problem, for some constant h:

    Weighted Weft-t Depth-h Circuit-SAT: Given a Boolean circuit C, with a mixture of fanin-2 and unbounded-fanin gates. The number unbounded-fanin gates along any path to the root is at most t, and the total depth (fanin-2 and unbounded-fanin) is at most h. Does C have a satisfying assignment of Hamming weight k?

See W[1] for the definition of fixed-parameter reducibility.

Defined in [DF99].

Contained in W[SAT] and in W*[t].

W*[t]: W[t] With Parameter-Dependent Depth

Same as W[t], except that now the circuit depth can depend on the parameter k rather than being constant. (The number of unbounded-fanin gates along any path to the root is still at most t.)

W*[1] = W[1] [DFT96], and W*[2] = W[2] [DF97], but the problem is open for larger t.

Retrieved from "https://complexityzoo.net/index.php?title=Complexity_Zoo:W&oldid=6467"