0
$\begingroup$

Our teacher gave us the following statement and we were wondering what is wrong with it.

Consider an array $A$ of $n$ distinct numbers. Since there are $n!$ permutations of $A$, we cannot check for each permutation whether it is sorted, in a total time which is polynomial in $n$.
Therefore, sorting $A$ cannot be in $P$.

Obviously this is wrong.
My friend thought it should just be: therefore sorting $A$ cannot be in $NP$.
Is this correct or are we thinking about it to easily?

$\endgroup$
  • $\begingroup$ You apparently know that the statement is wrong? Are you asking why this reasoning is wrong? $\endgroup$ – Albjenow Jan 9 at 13:12
  • $\begingroup$ Checking all the permutations is not polynomial that's what the statement is saying. It does not say that sorting is not in P. May be there is another polynomial time algorithm for sorting? Indeed, we know there is. $\endgroup$ – zdm Jan 9 at 16:22
  • $\begingroup$ @Albjenow Yes we were given that their is a mistake in the reasoning, and i was wondering what should be changed in the reasoning/argument to make a correct statement $\endgroup$ – NotRikBurgers Jan 9 at 16:38
3
$\begingroup$

Very simple: We can sort an array without checking every possible permutation. (Many times we don’t check any permutation of the array, we just re-arrange the order of items so we can guarantee the array is sorted, without ever checking it. )

$\endgroup$
3
$\begingroup$

Since $P \subseteq NP$, if the statement is false, it cannot become true by changing $P$ to $NP$.

What your teacher is doing here is trying to illustrate a very common fallacy amongst beginning CS-learners. He is giving one potential way to solve a problem, and he notes that this way needs more resources than we want to make available (sometimes it is instead: involes a non-computable subroutine). However, this says nothing at all about the complexity of the problem. Maybe that algorithm is simply not a good algorithm for the problem. Since, as you should know, sorting can be done in (less than) quadratic time, indeed trying out all permutations is a very bad way to sort a list.

To actually show that a problem is hard we need instead to reason about all potential algorithms, which is very difficult. Thus, we usually just recycle previous impossibility results via reductions. Sorting, however, comes with an innate lower bound: As long as we are dealing with an "unstructured" data type only allowing pairwise comparison, we cannot do better than $O(n \log n)$ by an information-theoretic argument.

$\endgroup$
  • $\begingroup$ +1. To the OP, a particularly exciting example of this to think about - where it's not at all obvious that the 'naive' approach is suboptimal (to put it incredibly mildly!) - is the fact that PRIMES is in P, despite the 'naive' approach being clearly non-polynomial. $\endgroup$ – Noah Schweber Jan 9 at 17:17

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.