Class Description

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.

Linked From

para-NL: Parameterized Nondeterministic Logspace

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.

More about...