<p>A counterexample to this Murphy's Law could actually be the famous paper</p>

<p><em>Baker, Theodore; Gill, John; Solovay, Robert</em>, <a href="http://dx.doi.org/10.1137/0204037" rel="nofollow noreferrer"><strong>Relativizations of the <span class="math-container">$\cal P=?\cal N\cal P$</span> question</strong></a>, SIAM J. Comput. 4, 431-442 (1975). <a href="https://zbmath.org/?q=an:0323.68033" rel="nofollow noreferrer">ZBL0323.68033</a>.</p>

<p>It shows that the <span class="math-container">$P=^? NP$</span> question is </p>

<ul>
<li><strong>hard</strong>: you cannot solve it with relativizable techniques; but also</li>
<li><strong>easy</strong>: we can establish <span class="math-container">$P^A= NP^A$</span> for some oracles <span class="math-container">$A$</span>, and <span class="math-container">$P^B \ne NP^B$</span> for some oracles <span class="math-container">$B$</span>, so now we just have to figure out what whether a trivial oracle is more like <span class="math-container">$A$</span> or like <span class="math-container">$B$</span>... </li>
</ul>

CC BY-SA 4.0
2018-11-07T00:31:09.953Z
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.
Yonatan N
CC BY-SA 4.0
2018-11-07T06:29:36.807Z
It's both, @YonatanN see bullet points 1 and 2
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2018-11-06T06:03:28.990Z
2018-11-06T06:03:28.990Z
Bjørn Kjos-Hanssen
<p>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 <span class="math-container">$P\overset?=NP$</span> 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.</p>

<p>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 <span class="math-container">$P\overset?=NP$</span> most challenging without causing inconsistencies?</p>

CC BY-SA 4.0
2018-11-05T19:14:54.677Z
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?
Joshua Grochow
CC BY-SA 4.0
2018-11-05T22:30:11.267Z
Interesting thought. I guess I hadn't considered independence results. I was thinking mostly of questions about the equality or separation of complexity classes.
Stop Harming the Community
CC BY-SA 4.0
2018-11-06T20:06:26.137Z
For those of us less familiar - could you give some examples of the separations/collapses you are talking about?
Holden Lee
<cc.complexity-theory><p-vs-np>
Is Murphy's Law of Complexity Theory consistent? What separations/collapses does it imply?
Stop Harming the Community
# Is Murphy's Law of Complexity Theory consistent? What separations/collapses does it imply?

(Asked by: username_0 on 2018-11-05)

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?

**Tags:** cc.complexity-theory, p-vs-np
> **Comments:**
> **username_1**: 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?  
> **username_0**: Interesting thought. I guess I hadn't considered independence results. I was thinking mostly of questions about the equality or separation of complexity classes.  
> **username_2**: For those of us less familiar - could you give some examples of the separations/collapses you are talking about?  

---

## 1 answers

### Answer by username_3 on 2018-11-06. Score: 3

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**](http://dx.doi.org/10.1137/0204037), SIAM J. Comput. 4, 431-442 (1975). [ZBL0323.68033](https://zbmath.org/?q=an:0323.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$...

> **Comments:**
> **username_4**: 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.  
> **username_3**: It's both, @YonatanN see bullet points 1 and 2  

---

