Class Description

Few: FewP With Flexible Acceptance Mechanism

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

  1. The number of accepting paths a is bounded by a polynomial in the size of the input x.
  2. 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

  1. If the answer is 'no,' then all computation paths reject.
  2. 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

  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.

More about...