$\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$ – Joshua Grochow Feb 7 '14 at 18:45
  • $\begingroup$ Lets replace FewP with UP_k, EP and etc.. $\endgroup$ – Tayfun Pay Feb 7 '14 at 19:03
  • $\begingroup$ @JoshuaGrochow It is possible that $\mathsf{fewP=NP}$ but $\mathsf{UP \ne fewP}$ $\endgroup$ – Mohammad Al-Turkistany Feb 7 '14 at 20:15
  • $\begingroup$ @JoshuaGrochow For instance, any result implying P=NP would also imply fewP=NP. Such results does not answer my question. $\endgroup$ – Mohammad Al-Turkistany Feb 7 '14 at 20:41
  • 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$ – Joshua Grochow Feb 8 '14 at 1:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.