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?


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.