Class Description

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:

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

Defined in [DF99].

Contains W[SAT].

Linked From

AW[P]: Alternating W[P]

Same as AW[SAT] but with 'circuit' instead of 'formula.'

Has the same relation to AW[SAT] as W[P] has to W[SAT].

Defined in [DF99].

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:

More about...


FPR: Fixed-Parameter Randomized

Has the same relation to FPT as RP does to P.

Defined in [AR01], where it was shown that, if the Resolution proof system is automatizable (that is, if a refutation can always be found in time polynomial in the length of the shortest refutation), then W[P] is contained in FPR.

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:

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