# What is wrong with the following $P$ problem?

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?

• You apparently know that the statement is wrong? Are you asking why this reasoning is wrong? – Albjenow Jan 9 at 13:12
• 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. – zdm Jan 9 at 16:22
• @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 – NotRikBurgers Jan 9 at 16:38

Since $$P \subseteq NP$$, if the statement is false, it cannot become true by changing $$P$$ to $$NP$$.
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.