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