Class Description

FewEXP: NEXP With Few Witnesses

The class of decision problems solvable by an NEXP machine such that, given a "yes" instance, no more than an exponential number of computation paths accept.

Contained in MIP[NPFewEXP] (MIP where provers are not unbounded in computational power, but are limited to NPFewEXP) [AKS+94].

Alternatively, FewEXP can refer to the sparsity of accepting paths in a given instance. In [AKR+03], the authors show that the conjectures "FewEXP search instances are EXP-solvable" and "FewEXP decision instances are EXP/poly-solvable" are equivalent. That is, for all NEXP machines , the following conditions are equivalent:

  1. There exists an EXP machine such that if given a string , accepts and has exponentially bounded accepting paths, then produces one such path.
  2. There exists an EXP/poly machine which accepts a string if and only accepts.

Linked From

No class.