What is wrong with the following $P$ problem?
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. )