Class Description

XNLP: Fixed-Parameter Nondeterministic Logspace and Polytime 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)) and time O(f(k) n^c), 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(n^f(k)).

Without the nondeterminism, this would also be contained in FPT, as the runtime is fixed-parameter tractable. But, it is nondeterministic.

Reference: [2]

Linked From

No class.