Class Description

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

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,k1,...,kr) (r,k1,...,kr parameters), 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 AW[*], and is contained in AW[P].

More about...