Class Description

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)

Linked From

No class.