5
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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? $\endgroup$ – Joshua Grochow Nov 5 '18 at 19:14
  • $\begingroup$ Interesting thought. I guess I hadn't considered independence results. I was thinking mostly of questions about the equality or separation of complexity classes. $\endgroup$ – rockwalrus Nov 5 '18 at 22:30
  • 4
    $\begingroup$ For those of us less familiar - could you give some examples of the separations/collapses you are talking about? $\endgroup$ – Holden Lee Nov 6 '18 at 20:06
3
$\begingroup$

A counterexample to this Murphy's Law could actually be the famous paper

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

  • hard: you cannot solve it with relativizable techniques; but also
  • 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$... 🙂
$\endgroup$
  • 2
    $\begingroup$ Is this a counterexample or an example? I think a common interpretation of that result is "nonrelativizing approaches won't work either way", which to me feels like a negative. $\endgroup$ – Yonatan N Nov 7 '18 at 0:31
  • $\begingroup$ It's both, @YonatanN see bullet points 1 and 2 $\endgroup$ – Bjørn Kjos-Hanssen Nov 7 '18 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.