Can someone pelase give a counter example of it? If a problem is in NP then there is no known polynomial time algorithm to solve it

Question

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.

Answer 1

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.