Class Description

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]

Linked From

para-L: Parameterized Logspace

para- version of L. Equivalent to DSPACE(f(k)+log(n)) for some computable function f. Compare with slicewise parameterized logspace, XL.

Parameterized vertex cover (is there a vertex cover of size at most k) is complete for para-L. (Elberfeld et al, 2012)

More about...


para-NL[f log]: Parameterized Nondeterministic Logspace

Like para-NL, but where the number of nondeterministic branches is bounded by O(f(k) log(n)).

A natural complete is problem parameterized distance: is there a path on directed graph G from vertex s to v, of length at most k? (Elberfeld et al, 2012)

para-NL[f log] is contained within XL, slicewise logspace.

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