Class Description

para-: Parameterized Complexity

The para- prefix indicates that a complexity class is parameterized by some other measure of complexity. Specifically, a language L is in the parameterized class para-C, if there is an alphabet A and a computable function pi(k) -> A*, such that every (Q,k) is in para-L if and only if (Q,pi(k)) in L.

The prototypical example (as well the violation of the naming convention) is para-P, which is almost always known as FPT, which is equal to DTIME(f(k)n^c) for some constant c.

Space-parameterized examples include para-L and para-NL, which are equal to DSPACE(f(k)+log(n)) and NDSPACE(f(k)+log(n)), respectively.

Compare with the slicewise complexity classes X-, such as X-.

Discussed in:J. Flum and M. Grohe. Describing parameterized complexity classes. Information and Computation.andElberfeld M., Stockhusen C., Tantau T. (2012) On the Space Complexity of Parameterized Problems.

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


para-P: Parameterized Polynomial time.

para-P is a less common name for FPT, but in line with other para- classes naming conventions. Its slicewise counterpart is still called XP.

More about...