$\mathsf{fewP}$ ($\mathsf{NP}$ with few witnesses, see the zoo) is one of the important ambiguity-bounded sub-classes of $\mathsf{NP}$. There are interesting natural problems in this class that are believed to be good candidates for problems in $\mathsf{NPI}$-intermediate such as Beltway problem and the Turnpike problem. Informally, $\mathsf{fewP}$ is the class of $\mathsf{NP}$ problems with polynomialy-bounded number of solutions.

$\mathsf{FewP}$ is defined as:

The class of decision problems solvable by an $\mathsf{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.

We known that $\mathsf{P} \subseteq \mathsf{UP} \subseteq \mathsf{fewP}\subseteq \mathsf{NP}$. It is an open problem whether any inclusion is strict. Specifically, $\mathsf{fewP}$ vs. $\mathsf{NP}$ is an open problem. The Complexity Zoo cites oracle results suggesting that all inclusions are strict and that $\mathsf{fewP}$ does not have a Turing-complete set.

Why do we believe that $\mathsf{fewP \ne NP}$?

Is there any unexpected consequence that follows from $\mathsf{fewP=NP}$ such as the collapse of the polynomial hierarchy or disproving any other widely believed complexity-theoretic conjecture?

  • 3
    $\begingroup$ It seems to me like the answers to cstheory.stackexchange.com/questions/3887/… are a superset of answers to this question. As there's currently only one answer to that question, I'm unfortunately not sure if this question will get any answers.... $\endgroup$ Commented Feb 7, 2014 at 18:45
  • $\begingroup$ Lets replace FewP with UP_k, EP and etc.. $\endgroup$
    – Tayfun Pay
    Commented Feb 7, 2014 at 19:03
  • $\begingroup$ @JoshuaGrochow It is possible that $\mathsf{fewP=NP}$ but $\mathsf{UP \ne fewP}$ $\endgroup$ Commented Feb 7, 2014 at 20:15
  • 4
    $\begingroup$ You're not asking for results that imply FewP=NP, you're asking for the converse: results that are implied by FewP=NP. So yes, it's possible that FewP=NP and $\mathsf{UP} \neq \mathsf{FewP}$, but that's not relevant to the OQ. You ask for evidence that $\mathsf{fewP} \neq \mathsf{NP}$. Any such evidence is also evidence that $\mathsf{UP} \neq \mathsf{NP}$ (and that $\mathsf{P} \neq \mathsf{NP}$, for that matter). In particular, that means that valid answers to this question are also valid answers to cstheory.stackexchange.com/questions/3887/… $\endgroup$ Commented Feb 8, 2014 at 1:27
  • 1
    $\begingroup$ @1.. By definition FewP languages are decided by NP machines in the usual way, there's just an extra requirement such machines must satisfy to say the language is in FewP. Just like UP w a different requirement. $\endgroup$ Commented Apr 6, 2021 at 18:02


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.