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 Mod_kL for all k>1.

Linked From

Mod_kL: Mod-k L

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

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

For any prime k, Mod_kL^ModkL = Mod_kL [HRV00].

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

More about...