Class Description

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

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

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

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