Class Description
Few: FewP With Flexible Acceptance Mechanism
The class of decision problems solvable by an NP machine such that
- The number of accepting paths a is bounded by a polynomial in the size of the input x.
- For some polynomial-time predicate Q, Q(x,a) is true if and only if the answer is 'yes.'
Also called FewPaths.
Defined in [CH89].
Contains FewP, and is contained in PFewP [Kob89] and in SPP [FFK94].
See also the survey [Tor90].
Linked From
FewP: NP With Few Witnesses
The class of decision problems solvable by an NP machine such that
- If the answer is 'no,' then all computation paths reject.
- If the answer is 'yes,' then at least one path accepts; furthermore, the number of accepting paths is upper-bounded by a polynomial in n, the size of the input.
Defined in [AR88].
Is contained in ⊕P [CH89].
There exists an oracle relative to which P, UP, FewP, and NP are all distinct [Rub88].
Also, there exists an oracle relative to which FewP does not have a Turing-complete set [HJV93].
Contained in Few.
See also the survey [Tor90].
More about...
LogFew: Logspace-Bounded Few
The class of decision problems solvable by an NL machine such that
- The number of accepting paths on input x is f(x), and
- 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.
More about...