patternMajor
Proof Complexity of a Proof or Disproof of P = NP
Viewed 0 times
disproofcomplexityproof
Problem
Has there been any research on the proof complexity of a resolution to the P=NP problem? If not, given the lack of progress on the problem, would it be unreasonable to conjecture that any proof that resolves the P=NP problem will require a super-polynomial number of steps?
Solution
Proof complexity only makes sense when there is a sequence of statements depending on a parameter $n$. For example, the proposition $\mathsf{PHP}_n$ states (informally) that there is no bijection $[n+1] \to [n]$. This sequence of propositions is hard for certain propositional proof systems.
The statement $\mathsf{P} \neq \mathsf{NP}$ is a single statement, so you can't apply proof complexity to it directly. However, the following sequence of statements does make sense, for particular functions $s(n)$: "there is no circuit of size $s(n)$ correctly solving SAT for instances of length $n$". This has been considered in the literature, for example by Razborov (who considered the setting of uniform proof complexity, i.e., bounded arithmetic).
The statement $\mathsf{P} \neq \mathsf{NP}$ is a single statement, so you can't apply proof complexity to it directly. However, the following sequence of statements does make sense, for particular functions $s(n)$: "there is no circuit of size $s(n)$ correctly solving SAT for instances of length $n$". This has been considered in the literature, for example by Razborov (who considered the setting of uniform proof complexity, i.e., bounded arithmetic).
Context
StackExchange Computer Science Q#66603, answer score: 24
Revisions (0)
No revisions yet.