6
$\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?

Improve this question
$\endgroup$
3
  • 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, 2018 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$
    – Stop Harming the Community
    Nov 5, 2018 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, 2018 at 20:06

1 Answer 1

Reset to default
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$... 🙂
Improve this answer
$\endgroup$
2
  • 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, 2018 at 0:31
  • $\begingroup$ It's both, @YonatanN see bullet points 1 and 2 $\endgroup$
    – Bjørn Kjos-Hanssen ♦
    Nov 7, 2018 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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