Class Description

XP: Fixed-Parameter Tractable for Each Parameter

The class of decision problems of the form (x,k) (k a parameter) that are solvable in time O(|x|f(k)) for some function f. The algorithm used may depend on k.

Defined in [DF99].

Contains XPuniform.

Strictly contains FPT (by diagonalization).

Linked From

para-P: Parameterized Polynomial time.

para-P is a less common name for FPT, but in line with other para- classes naming conventions. Its slicewise counterpart is still called XP.

More about...


XL: Fixed-Parameter Logspace for Each Parameter

The class of decision problems of the form (x,k) (k a parameter) that are solvable in space O(f(k)*log(n)) for some function f. The algorithm used may depend on k.

Analogous to XP, as L is to P.

A natural XL complete problem is p-MDFA-ACCEPTANCE: Given a finite two-way deterministic automation A with k heads, and given a string x, does A accept x?

Reference: [1]

More about...


XNL: Fixed-Parameter Nondeterministic Logspace for Each Parameter

The class of decision problems of the form (x,k) (k a parameter) that are solvable in space O(f(k) log(n)), by a nondeterministic Turing machine, for some function f. The algorithm used may depend on k.

Analogous to XP, as NL is to P. Nondeterministic version of XL.

A natural XNL complete problem is p-MNFA-ACCEPTANCE: Given a finite two-way nondeterministic automation A with k heads, and given a string x, does A accept x?


More about...


XPuniform: Uniform XP

Same as XP except that the algorithm used must be the same for each k (though it can take k as input).

Defined in [DF99].

More about...