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