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

Asked 12/12, 2012 at 10:18 Answered 12/12, 2012 at 11:4

Solved algorithm sorting np-complete np p-np

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.

Serotherapy answered 12/12, 2012 at 10:18 Comment(2)

THe inclusion "NP is in NP-Complete" is false, the good inclusion is "NP-Complete is in NP" because NP-complete means "in NP but not in P (assuming P!=NP)". – Hyperphagia 12/12, 2012 at 13:42

@Thomash's comment hits the nail on the head. That and the fact that P, NP etc. apply to problems, not algorithms for problems, as pointed out by COME FROM. – Pickmeup 14/12, 2012 at 10:2

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 :

enter image description here

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 (you can solve the problem yourself and compare to the right answer in P time).

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.

Fearsome answered 12/12, 2012 at 11:4 Comment(5)

. sorting is a permutation on the list of numbers which suggests a non polynomial time brute force algorithm. so it can be in NP class. – Hypochondriac 18/12, 2015 at 5:10

@user1198898 It is NP, but not for the reasons you list. – Fearsome 18/12, 2015 at 20:54

well what if I told you , sorting can't be part of any of these classes ? – Hypochondriac 20/12, 2015 at 15:43

@user1198898 In that case, I will recommend a few reads, like this one. – Fearsome 20/12, 2015 at 22:50

yes , the document you showed tells sorting as a decision problem is NP-Complete. It means a program can make a decision Yes/No. The question above posted asks if sorting is P or NP which is actually undefined since only decision problems comprise of P and NP and sorting isn't part of any! The question above might have to be rephrased . thats what I mean – Hypochondriac 21/12, 2015 at 7:5

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

Consume answered 12/12, 2012 at 10:30 Comment(3)

Good answer, fantastic username :) – Pickmeup 14/12, 2012 at 9:59

to be precise decision problems – Hypochondriac 20/12, 2015 at 15:43

@Hypochondriac NP-hard is not limited to decision problems. – Kinson 26/5, 2021 at 17:23

Recommended topics

Hot tags