Class Description

ModZkL: Restricted ModkL

The class of decision problems solvable by a nondeterministic logspace Turing machine, such that

  1. If the answer is "yes," then the number of accepting paths is not congruent to 0 mod k.
  2. If the answer is "no," then there are no accepting paths.

Defined in [BDH+92], where it was also shown that ModZkL contains LogFewNL for all k>1.

Contained in ModkL and in NL.

Linked From

LogFewNL: Logspace-Bounded FewP

Same as FewP but for logspace-bounded (i.e. NL) machines.

Defined in [BDH+92], where it was also shown that LogFewNL is contained in ModZkL for all k>1.

More about...