-2

P!=NP seems to be a very hard question. But I didn't know whether anyone has quantified its hardness. So I ask the following question. Given a suitable formal system F, is finding a proof with less than n symbols for P != NP an NP-complete problem? (Asymptotic time of finding proof with respect to the proof length.)

It's clearly in NP since given a proof of length n, we can use rules in formal system F to determine whether each line follows from the above. However, it's not clear o me whether it should be NP-Complete.

If this problem is NP-Complete, then to prove that P != NP is practically impossible. The implication is that we can settle P != NP only if P = NP.

Tianshu Yu
  • 25
  • 1
    It is impossible to judge the hardness of a problem that has not been solved yet. It is however known that most of the traditional proof techniques do not work which can be shown by considering oracles. Also note that the proof of a single statement can never be NP-complete. It is a single instance of a decision problem and has therefore complexity $O(1)$ by definition. – Peter Dec 15 '21 at 08:51
  • 1
    Additionally, "NP-complete" does not mean that no particular decision-problem of this kind can practially be solved (the hardness is only about the worst case) and "P"-problems can be infeasible in practice to be solved : The degree can be very high or high constants can be involved. – Peter Dec 15 '21 at 08:56

1 Answers1

1

No, it's certainly not $NP$-complete; it's in $P$.

Either there is a proof of $P \; != NP$ or there isn't (if in fact $P \; != NP$, there's no guarantee that there is a proof of that). If there is a proof, there is a proof of a certain length $N$. Then for any $n > N$, to exhibit a proof of length $< n$ takes constant time (namely, you just print out THAT proof). If there is no proof, then of course you can't exhibit such a proof, and the answer (again, in constant time) is just "No, it can't be done".

Robert Israel
  • 448,999