Sunday, April 14, 2019

Good article, terrible headline

About a month ago (after my P NP poll appeared) I got email from Jacob Aron asking me some questions about it. One thing he was excited about was that the number of people who thought P vs NP would be solved in the next decade had increased from 11% to 22%. I told him that this also surprised me and there had been no major advances to warrant that increase.

Then the article came out. Here is the pointer to the headline and the first few lines, the rest is behind a paywall


You may notice that the headline is

We could solve the biggest problem in math in the next decade

I emailed Jacob to send me the article, which he did. The article was fine, even quoting me as saying that the increase of people who thought it would be solved soon was unwarranted.

1) So, article fine, headline terrible.

2)  A more honest headline would be

The Complexity Theory Community slightly more optimistic about when P vs NP will be resolved for no apparent reason.

3) More bad science:here

Headline is

Turing's Oracle: The computer that goes beyond logic

I think the article was about how a Turing Machine with an oracle for HALT can solve HALT. (If I am wrong about this let me know in the comments and I'll correct it.)

4) More bad science:here


Finally, a problem that only Quantum Computers will ever be able to solve.

This was about the oracle such that BQP is not in PH. Really!

5) I invite you to add your own.

6) OKAY, so why is the press SO BAD at reporting on our field? And is it just our field? I have one explanation, though I am sure there are many.

Our field is about showing the LIMITS of computation. Its hard to make that sexy so they ... lie? exaggerate. They themselves don't really understand our field? Note:

To explain to someone who does not really know CS why its important to have an oracle where BQP is not in PH is hard

To explain this to someone IN CS but not in Theory is still hard!

To explain this to someone IN CS and even in CS Theory, but not complexity (e.g., algorithms) might be hard, though it may depend on the person.

7) The old saying is `I don't care if you get the story wrong so long as you spell my name right' And indeed, they did spell my name right. So there is that! But more seriously and less about me or even the article that refers to my poll--- is it bad that science reporting is often wrong?


  1. It not just TCS, but science in general. See for example this amazing twitter feed.

  2. It's probably not the writer's fault, as headlines are the exclusive responsibility of editors. I learned the hard way that even when I write opinion pieces, I have very limited control over their headlines.

    1. AH- that could explain why the article (which mentioned my poll) is actually okay, but the headline is not.

      As for Turing's Oracle and the Quantum paper--- article and headline both terrible.

  3. This would be a good to bring up with the math and science journalists like @evelynjlamb and @CaraSantaMaria.

    Also, isn't New Science notorious for getting things wrong? Or am I just passing along insidious gossip?

  4. The headline makes perfect sense from THEIR perspective. It gets you to pay for the article and then you find out the truth. It is a teaser to get you interested.

  5. Now you know what Trump's been talking about. Media = Fake news. They like exaggerating things just to increase their readership.

  6. I don't think it is that hard to explain the significance of an oracle such that BQP is not in PH. I could explain it to my friends in undergrad algorithms class.

    One can think about NP as exists-P, and if you generalize this to arbitrary sequences of quantifiers you get PH. Just as we believe NP (exists-P) is different from coNP (forall-P), we believe that PH doesn't collapse.

    Now, the natural question is where does BQP go? (On a sidenote, we know that BPP is in PH. One implication of this is that if P=NP, then P=BPP or randomness doesn't give an "edge.") If P=NP, does it also imply that BQP=P (quantumness doesn't provide an edge)? An easier question is, is BQP in PH? Another perspective is, one can think about PH in terms of bounded games, can we think about BQP as a game? We think the answer is NO. But since we cannot even prove that P ≠ PSPACE, we cannot prove that BQP is not in PH. The best we can hope for right now is a relativized world where this holds. Recall that if this does hold, then it holds in at least one relativised world.