Class Description

LogFew: Logspace-Bounded Few

The class of decision problems solvable by an NL machine such that

  1. The number of accepting paths on input x is f(x), and
  2. The answer is 'yes' if and only if R(x,f(x))=1, where R is some predicate computable in L.

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

Linked From

ModkL: Mod-k L

Has the same relation to L as ModkP does to P.

For any prime k, ModkL contains SL [KW93].

For any prime k, ModkLModkL = ModkL [HRV00].

For any k>1, contains LogFew [BDH+92].

More about...