# Statement that inequality of P and NP obstructs finding a proof of their separation

In this set of video lectures, Prof. Mulmuley emphasizes several times that P vs. NP is a very deep philosophical question at the core of Mathematics and that the fact that the two classes are not equal stands as an obstruction to proving that they are not equal (I paraphrase here, according to my limited understanding).

Now, I have two difficulties with this idea. Firstly, it was presented as though it were common mainstream belief (akin to the belief that P != NP). I did not come across this idea before, being expressed explicitly in this manner (maybe this is lack of exposure from my side).

The second difficulty is a bit more technical. P != NP tells something about hardness of finding proofs for provable statements, it does not saying anything about existence vs. non-existence of such proofs. Said naively, if P != NP, then this fact should not obstruct the existence of an easy, verifiable proof of this fact (other facts may provide such an obstruction though).

Am I misunderstanding something?

Note: I was not really sure if this question belongs to tcs.SE but I couldn't find a more suitable choice.

• Soon there will be cs.stackexchange.com (private beta right now). This should be perfectly suited. If you want I can invite you to the private beta, send me an email (see my profile => website). – Gopi Mar 19 '12 at 14:23
• I think the questions are fine for csthoery, though the post may need to editing. – Kaveh Mar 19 '12 at 14:30
• @Kaveh Tell me what needs editing and I'll do it right away! :-) – aelguindy Mar 19 '12 at 14:31
• P != NP does not preclude the existence of an easy verifiable proof of that fact, but morally (i.e. for various reasons this isn't a formal statement), it says that the mere existence of an easy verifiable proof of P != NP does not mean that such a proof should be easy to find. There could be an elegant, easily verifiable proof and still it could be extremely difficult to find. – Aaron Roth Mar 19 '12 at 16:09
• For some more GCT video lectures, go here intractability.princeton.edu/blog/2009/12/… – Tyson Williams Mar 20 '12 at 1:59

I also think that what was meant might have been obstructions akin to the natural proofs barrier of Razborov and Rudich. The barrier on a high level shows that current methods of proving circuit lower bounds are "self-defeating" when applied to the P vs NP problem. Suppose you want to prove that SAT is hard by showing that it satisfies some predicate which is not satisfied by problems in P. Suppose the predicate is satisfied by most boolean functions (the largeness property) and can be computed in time $2^{O(n)}$ on functions that take $n$ inputs, when given the $2^n$-size truth table of the function (the constructivity property). Razborov and Rudich show that if such a predicate exists, then there are no strong pseudorandom number generators. So the existence of the object we're trying to use to separate P from NP would itself imply a statement in the spirit of P=NP.