1
$\begingroup$

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?

$\endgroup$

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.