Class Description

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(2^o(n)).

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

Linked From

AW[SAT]: Alternating W[SAT]

Basically has the same relation to W[SAT] as PSPACE does to NP.

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

Parameterized QBFSAT: Given a Boolean formula F (with no restriction on depth), over disjoint variable sets S₁,...,S_r. Does there exist an assignment to S₁ of Hamming weight k₁, such that for all assignments to S₂ of Hamming weight k₂, etc. (alternating 'there exists' and 'for all'), F is satisfied?

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

Defined in [DF99].

Contains AW[*], and is contained in AW[P].

More about...

EPTAS: Efficient Polynomial-Time Approximation Scheme

The class of optimization problems such that, given an instance of length n, we can find a solution within a factor 1+ε of the optimum in time f(ε)p(n), where p is a polynomial and f is arbitrary.

Contains FPTAS and is contained in PTAS.

Defined in [CT97], where the following was also shown:

• If FPT = XP_uniform then EPTAS = PTAS.
• If EPTAS = PTAS then FPT = W[P].
• If FPT is strictly contained in W[1], then there is a natural problem that is in PTAS but not in EPTAS. (See [CT97] for the statement of the problem, since it's not that natural.)

More about...

FPT: Fixed-Parameter Tractable

The class of decision problems of the form (x,k), k a parameter, that are solvable in time f(k)p(|x|), where f is arbitrary and p is a polynomial.

The basic class of the theory of fixed-parameter tractability, as described by Downey and Fellows [DF99].

To separate FPT and W[2], one could show there is no proof system for CNF formulae that admits proofs of size f(k)n^O(1), where f is a computable function and n is the size of the formula.

Contained in FPT_nu, W[1], and FPR.

Contains FPTAS [CC97], as well as FPT_su.

Contains EPTAS unless FPT = W[1] [Baz95].

More about...

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].

More about...

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].

More about...

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].

More about...