<p>What if we had an oracle for solving all NP problems which has exactly one solution in polynomial time.</p>

<p>The oracle fails if the NP problem has more than 1 solution.
The question is can we use this oracle to solve all NP problems in polynomial time even if they have multiple solutions?</p>

CC BY-SA 3.0
2016-02-08T12:28:45.550Z
IIUC, you are asking if $NP \subseteq P^{UP}$. See the [UP](https://en.wikipedia.org/wiki/UP_(complexity)).
Kaveh
CC BY-SA 3.0
2016-02-08T14:50:50.840Z
http://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/NP_is_as.pdf
Daniel Apon
CC BY-SA 3.0
2016-02-08T16:31:09.990Z
https://en.wikipedia.org/wiki/Valiant%E2%80%93Vazirani_theorem
Thomas Steinke
CC BY-SA 3.0
2016-02-09T11:15:08.193Z
Depending on what exactly "the oracle fails" means, the question may rather be if $\mathrm{NP}\subseteq\mathrm{P^{promiseUP}}$.
Emil Jeřábek
<cc.complexity-theory>
Oracle for NP complete problems
rajeesh
# Oracle for NP complete problems

(Asked by: username_0 on 2016-02-08)

What if we had an oracle for solving all NP problems which has exactly one solution in polynomial time.

The oracle fails if the NP problem has more than 1 solution.
The question is can we use this oracle to solve all NP problems in polynomial time even if they have multiple solutions?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: IIUC, you are asking if $NP \subseteq P^{UP}$. See the [UP](https://en.wikipedia.org/wiki/UP_(complexity)).  
> **username_2**: http://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/NP_is_as.pdf  
> **username_3**: https://en.wikipedia.org/wiki/Valiant%E2%80%93Vazirani_theorem  
> **username_4**: Depending on what exactly "the oracle fails" means, the question may rather be if $\mathrm{NP}\subseteq\mathrm{P^{promiseUP}}$.  

---

## 0 answers

