[xkjzhotw] P < NP proof approach

The obvious idea is, if P=NP then that leads to a contradiction.  The most promising area where a contradiction might happen is contradicting some other proven result in time complexity theory.  One such proven result is the time hierarchy: P < EXPTIME.

Take an NP problem suspected not to be in P, assume it to be in P, then use it as an oracle (running in polynomial time, not instantaneously as oracles typically do) while solving an EXPTIME problem.  Can the EXPTIME problem now be solved too quickly, breaking time hierarchy?  If so, that is a contradiction, so it must be that the original NP problem was not in P, so we have proved the existence of a problem in NP not in P, so P < NP.

The attractiveness of this approach is that there are many NP problems and many EXPTIME problems (though I'm not too familiar with class EXPTIME), so everyone can study a different pair, trying to get one to usefully increase the speed of the other.  Inspired by the PolyMath projects, setting a lot of people to work on a problem from different angles.

The oracle problem does not need to be NP-complete.  For example, suppose we assume that integer factorization (an NP problem that seems not to be NP-complete) is in P.  Then, use deterministic polynomial-time factoring as a subroutine in some EXPTIME problem and cause the latter to be solved too quickly.  The assumption that integer factorization is in P must have been false, thus establishing the existence of one problem in NP that is not in P.

Although the subroutine problem does not need to be NP-complete, NP-complete problems are the most difficult in NP, or equivalently, assuming one of them is in P gives you the most bang for the buck, the most powerful subroutine.

I don't think this approach runs into the uselessness of relativization proved in Baker-Gill-Solovay 1975.  That paper dealt with relativizations of the forms P^X and NP^X, but here we are doing EXPTIME^NP.

I suspect the biggest problem with this approach is that the gap between EXPTIME and P is very large, so it is hard to imagine an NP oracle reducing the running time of something in EXPTIME all the way down to P.  It might be provable that this is impossible even without proving anything about P versus NP.