can some sorting be P, NP, and NP-Complete?

Question

I am quite confused, and this is my thought after some reading:

P is in NP and NP is in NP-Complete. Therefore, all P could be in NP and NP-Complete?

Does that mean there are sorting algorithms that could be NP and NP-Complete?

Hope this doesn't sound too stupid.

Answer 1

First things first :

P is in NP; NP is in NP-Complete. therefore, all P could be in NP and NP-Complete?

Is quite a statement because what you are saying implies P=NP . No one has been able to prove this or otherwise. So here is the state of affairs :

Most of the people believe that P!=NP. Quoting from Wikipedia :

In a 2002 poll of 100 researchers, 61 believed the answer to be no, 9 believed the answer is yes, and 22 were unsure; 8 believed the question may be independent of the currently accepted axioms and therefore is impossible to prove or disprove.

A simple way to understand is this : Suppose you are given a solution to some problem. If you can verify that whether the solution is correct or not in polynomial time, then the problem is NP. Clearly, every problem that can be solved in polynomial time (P) is in NP. Right now we have several problems that can be verified in polynomial time but cannot be solved in the same. We are not sure that whether there can never be a polynomial time solution or are we not able to figure it out just yet.

---

Sorting Numbers

• Given a list of numbers, you can verify that whether the list is sorted or not in polynomial time, so the problem is clearly NP.

• There are known algorithms to sort a list of numbers in polynomial time. (Bubble sort O(n^2) etc. ). Thus the problem is P.

Hope this helps.

Consider giving this blog a read.

Answer 2

P, NP, NP-hard and NP-complete are complexity classes of problems; they characterize a problem, not an algorithm.