Class Description

G[t]: Stratification of Fixed-Parameter Tractable Problems

(Basically) the class of decision problems of the form (x,k) (k a parameter), that are solvable by a parameterized family of circuits with unbounded fanin and depth t. A uniformity condition may also be imposed.

Defined in [DF99], which should be consulted for the full definition.

Uniform G[P] (i.e. with no restriction on depth) is equal to FPT.

Linked From

No class.