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?
para- version of NL. Equivalent to NDSPACE(f(k)+log(n)) for some computable function f. Compare with slicewise parameterized nondeterministic logspace, XNL.
It seems open whether there are natural complete problems for para-NL. However, the related class para-NL[f log] has many natural complete problems.
The class of decision problems of the form (x,k) (k a parameter) that are solvable in space O(f(k) log(n)) and time O(f(k) nc), by a nondeterministic Turing machine, for some function f. The algorithm used may depend on k.
Contained in XNL, which has the same space restriction but allows runtimes of O(nf(k)).
Without the nondeterminism, this would also be contained in FPT, as the runtime is fixed-parameter tractable. But, it is nondeterministic.
Reference: [2]