Class Description

AW[t]: Alternating W[t]

Has the same relation to W[t] as PSPACE does to NP.

Same as AW[SAT], except that the formula F can have depth at most t.

Defined in [DF99].

Contained in AW[*].

[DFT98] show that for all t, AW[t] = AW[*].

Linked From

AW[*]: Alternating W[*]

The union of AW[t] over all t.

More about...