Is there any known polynomial time algorithm to solve a problem which that problem is in NP. I was told is False but can't think of any counter example now.

  • $\begingroup$ An algorithm to solve a problem, or to solve a freely chosen member of a class of problems? $\endgroup$ Dec 6 '19 at 23:26
  • $\begingroup$ I’m assuming by NP you mean NP complete? $\endgroup$ Dec 6 '19 at 23:31
  • $\begingroup$ @brycekille why ? $\endgroup$
    – user95432
    Dec 6 '19 at 23:37
  • $\begingroup$ @user95432 because P is a subset of NP. $\endgroup$ Dec 6 '19 at 23:43
  • $\begingroup$ If p!=np and factoring is proven to only be in NP. Then there is no poly-time algorithm to solve it on a classical machine. Remember, I said classical. $\endgroup$ Dec 7 '19 at 0:55

NP is the class of decision problems where any instance with an answer "YES" has a proof that the answer is YES which can be checked in polynomial time. NP contains all problems that are solvable in polynomial time. Therefore there are many problems in NP with known polynomial time algorithms.

If you are talking about NP-complete problems, that's a whole different matter. There is (at this point in time) no NP-complete problem with a known polynomial time algorithm to solve it.

Someone might find a proof that for an NP-complete problem there is no NP-complete problem with a polynomial time algorithm to solve it - not just no known algorithm, but no algoritm at all.

On the other hand someone might actually find an NP-complete that can be solved in polynomial time. It is unlikely though.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.