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[NP^FewEXP] (MIP where provers are not unbounded in computational power, but are limited to NP^FewEXP) [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 ${\displaystyle N}$, the following conditions are equivalent:

1. There exists an EXP machine ${\displaystyle M}$ such that if given a string ${\displaystyle x}$, ${\displaystyle N(x)}$ accepts and has exponentially bounded accepting paths, then ${\displaystyle M(x)}$ produces one such path.
2. There exists an EXP/poly machine ${\displaystyle M}$ which accepts a string ${\displaystyle x}$ if and only ${\displaystyle N(x)}$ accepts.

Linked From

No class.