# Is Murphy's Law of Complexity Theory consistent? What separations/collapses does it imply?

A decade ago I observed what I dub "Murphy's Law of Complexity Theory": whenever a new separation or collapse is discovered, the question is answered in the direction that makes $$P\overset?=NP$$ most challenging to determine. I do not believe this rule has failed once in the intervening years. This leads me to wonder what the implications would be if the Law were actually true.

What questions could be answered using this conjecture? Are the answers consistent, or is there some set of questions such that they can't all be answered in the way that makes proving $$P\overset?=NP$$ most challenging without causing inconsistencies?

• Interesting question. Not sure how this applies to the question of whether P vs NP is independent of, say, ZFC though. For example, in this situation, we might think "most challenging" would be independence, since then resolving it would arguably be impossible. On the other hand, independence itself is some kind of resolution. And then there's Ben-David-Halevi, which says that if it's independent then NP is nearly contained in P. Does that satisfy your murphy's law? Nov 5, 2018 at 19:14
• Interesting thought. I guess I hadn't considered independence results. I was thinking mostly of questions about the equality or separation of complexity classes. Nov 5, 2018 at 22:30
• For those of us less familiar - could you give some examples of the separations/collapses you are talking about? Nov 6, 2018 at 20:06

Baker, Theodore; Gill, John; Solovay, Robert, Relativizations of the $$\cal P=?\cal N\cal P$$ question, SIAM J. Comput. 4, 431-442 (1975). ZBL0323.68033.
It shows that the $$P=^? NP$$ question is
• easy: we can establish $$P^A= NP^A$$ for some oracles $$A$$, and $$P^B \ne NP^B$$ for some oracles $$B$$, so now we just have to figure out what whether a trivial oracle is more like $$A$$ or like $$B$$... 🙂