Proof Complexity of a Proof or Disproof of P = NP

Problem Detail: 

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?

Asked By : Tony Johnson

Answered By : Jan Johannsen

It is known that any proof of super-polynomial circuit lower bounds (which are slightly stronger statements than $P\neq NP$) require super-polynomial, even exponential size proofs in weak proof systems like resolution. Generalizing this to stronger proof systems is a well known open problem.

See section 5 of this survey by A. Razborov where these things are shown.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/66603