<p>$\mathsf{fewP}$ ($\mathsf{NP}$ with few witnesses, see <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aF#fewp">the zoo</a>) 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. </p>

<p><a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aF#fewp">$\mathsf{FewP}$</a> is defined as:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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.</p>

<blockquote>
  <p>Why do we believe that $\mathsf{fewP \ne NP}$? </p>
</blockquote>

<p>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?</p>

CC BY-SA 3.0
2014-02-07T18:45:02.677Z
It seems to me like the answers to http://cstheory.stackexchange.com/questions/3887/consequences-of-up-equals-np 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....
Joshua Grochow
CC BY-SA 3.0
2014-02-07T19:03:56.400Z
Lets replace FewP with UP_k, EP and etc..
Tayfun Pay
CC BY-SA 3.0
2014-02-07T20:15:40.760Z
@JoshuaGrochow It is possible that $\mathsf{fewP=NP}$ but $\mathsf{UP \ne fewP}$
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-02-07T20:41:26.430Z
@JoshuaGrochow For instance, any result implying P=NP would also imply fewP=NP. Such results does not answer my question.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-02-08T01:27:47.347Z
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 http://cstheory.stackexchange.com/questions/3887/consequences-of-up-equals-np
Joshua Grochow
CC BY-SA 3.0
2014-02-08T07:55:21.180Z
@JoshuaGrochow I have no interest in evidence for $\mathsf{UP\ne NP}$.
Mohammad Al-Turkistany
CC BY-SA 4.0
2021-04-06T14:26:27.523Z
@JoshuaGrochow How is $\mathsf{FewP}\subseteq\mathsf{NP}$? Is 'Is there $k=\mathsf{poly}(n)$ witnesses for given probem?' $\mathsf{FewP}$-complete and we provide $k$ witnesses?
Turbo
CC BY-SA 4.0
2021-04-06T18:02:05.170Z
@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.
Joshua Grochow
<cc.complexity-theory><complexity-classes><conditional-results>
Why do we believe $\mathsf{fewP \ne NP}$?
Mohammad Al-Turkistany
# Why do we believe $\mathsf{fewP \ne NP}$?

(Asked by: username_0 on 2014-02-07)

$\mathsf{fewP}$ ($\mathsf{NP}$ with few witnesses, see [the zoo](https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aF#fewp)) 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}$](https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aF#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?

**Tags:** cc.complexity-theory, complexity-classes, conditional-results

> **Comments:**
> **username_1**: It seems to me like the answers to http://cstheory.stackexchange.com/questions/3887/consequences-of-up-equals-np 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....  
> **username_2**: Lets replace FewP with UP_k, EP and etc..  
> **username_0**: @JoshuaGrochow It is possible that $\mathsf{fewP=NP}$ but $\mathsf{UP \ne fewP}$  
> **username_0**: @JoshuaGrochow For instance, any result implying P=NP would also imply fewP=NP. Such results does not answer my question.  
> **username_1**: 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 http://cstheory.stackexchange.com/questions/3887/consequences-of-up-equals-np  
> **username_0**: @JoshuaGrochow I have no interest in evidence for $\mathsf{UP\ne NP}$.  
> **username_3**: @JoshuaGrochow How is $\mathsf{FewP}\subseteq\mathsf{NP}$? Is 'Is there $k=\mathsf{poly}(n)$ witnesses for given probem?' $\mathsf{FewP}$-complete and we provide $k$ witnesses?  
> **username_1**: @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.  

---

## 0 answers

