<p>Hm, its tough even to think of examples of claims about TCS that make it to the popular press. </p>

<p>One thing I have seen occasionally is the claim that factoring is NP-hard, when explaining cryptography. This is related to the less innocuous error of claiming that quantum computers can solve NP hard problems, but restricted to the context of cryptography, this is a relatively mild error. The point is just that we (users of cryptography) seem to believe that there is no efficient algorithm for solving the problem. The particular conjectures we use to justify this assertion are besides the point.</p>

CC BY-SA 3.0
2012-07-11T17:23:07.553Z
2012-07-11T17:23:07.553Z
Aaron Roth
<ul>
<li><p>claim by press: about things that grow "exponentially" ie claim of O(k^n)</p></li>
<li><p>actually true: often, a constant power O(n^k)</p></li>
<li><p>big picture: it grows fast enough, all right</p></li>
</ul>

CC BY-SA 3.0
2012-07-11T18:20:15.167Z
That's a nice one. I was thinking about that as well.
Suresh Venkat
CC BY-SA 3.0
2012-07-11T19:09:39.660Z
I actually keep one of these on my webpage: http://cg.scs.carleton.ca/~morin/misc/nortel/
Pat Morin
CC BY-SA 3.0
2012-07-11T20:40:21.020Z
Except in that case it DID make a difference :)
Suresh Venkat
CC BY-SA 3.0
2012-07-12T09:21:57.063Z
exponential has taken the meaning of anything  that grows superlinearly
ratchet freak
CC BY-SA 3.0
2012-10-19T13:22:35.713Z
The word _"exponential"_ is one of the most abused. Here are some examples I've seen: _"The number of goals scored by [some soccer player] has been growing exponentially from each season to the next"_,_"I've been able to improve my team working attitude in an exponential manner along the years"_,_"The number of channels available through satellite TV is exponential"_.
Giorgio Camerani
CC BY-SA 3.0
2012-07-11T17:20:22.063Z
2012-07-11T17:20:22.063Z
kena
<ul>
<li>Claim by press: First polynomial time algorithm for an important practical problem will necessarily change our lives, will be the next  best thing after sliced bread, etc.</li>
</ul>

<p>For examples, take any press article about the ellipsoid algorithm from the time it was discovered (great account of the story: <a href="http://www.springerlink.com/content/vh32532p5048062u/">http://www.springerlink.com/content/vh32532p5048062u/</a>). The press claimed that this new great mathematical discovery will affect everyone's lives, solve TSP (which they found especially ironic given how few traveling salesmen there were in the USSR!), turn crypto upside down, etc.</p>

<p>Then there is AKS, which in some reports was even implied to solve factoring..or at least to be an industry-changing innovation.</p>

<p>I am sure there are plenty more examples.</p>

<ul>
<li><p>Actually true: Polynomial time does not mean practical! Case in point: ellipsoid algorithm, sampling from high-dimensional convex bodies. Worst-case exponential time does not mean impractical. Case in point: simplex algorithm. When the new algorithm is merely the first deterministic polytime algorithm for a problem, this has even less relevance to practice.</p></li>
<li><p>Big picture: these results are breakthroughs, and at least the press gets people excited about them, even if it is for the wrong reasons. And much of the time a polynomial time algorithm eventually turns into a reasonably efficient algorithm. For example Gentry's homomorphic encryption scheme is not practical yet, but its running time has been improved significantly. Near-linear time solvers for SDD systems of equations seem to be well on the way to practicality but started off with a $\log^5 n$ factor hidden in the soft-oh notation.</p></li>
</ul>

CC BY-SA 3.0
2012-07-14T00:25:59.363Z
2012-07-14T00:25:59.363Z
Sasho Nikolov
<p>The popular press often gives the impression that the primary, if not the only, reason that computers are succeeding at more and more tasks (beating Kasparov at chess, beating Jennings at Jeopardy, etc.) is increased raw processing power.  Algorithmic advances are typically not given that much credit.</p>

<p>However, I'm ambivalent about whether insisting that algorithmic advances be given more weight is "pedantry."  On the one hand, I think that those of us who are more theoretically inclined can sometimes overstate the importance of algorithmic advances and only grudgingly admit the importance of increased processing power.  On the other hand, I do think the public should be better informed about the role of theoretical advances in solving practical problems.</p>

CC BY-SA 3.0
2012-07-14T07:16:02.453Z
I think it could be argued that "pedantry" is accurate.  Many people don't know the difference between hardware or software (really a surprising amount for me at least).  To the uninitiated, where exactly the improvement comes from could be classified as pedantry, even though we know that there are huge structural and conceptual differences.
SamM
CC BY-SA 3.0
2012-07-13T22:29:30.610Z
2012-07-13T22:29:30.610Z
Timothy Chow
<p>Scott Aaronson, while a foremost authority, seems to regularly take the media to task for not hairsplitting accurately. eg his recent column in the NYT article <a href="http://www.nytimes.com/2011/12/06/science/scott-aaronson-quantum-computing-promises-new-insights.html" rel="nofollow">"Quantum Computing Promises New Insights, Not Just Supermachines"</a> [italics added]</p>

<blockquote>
  <p>Struggling to shoehorn that mathematics into newspaper-friendly metaphors, <em>most popular writers describe a quantum computer as a magic machine that could process every possible answer in parallel,</em> rather than trying them one at a time. Supposedly, it could do that because, unlike today’s computers that manipulate bits, a quantum computer would manipulate quantum bits, or qubits, which can be 0 and 1 simultaneously.</p>
  
  <p>But that’s a crude way to visualize what a quantum computer does, and misses the most important part of the story. When you measure a quantum computer’s output, you see just a single, random answer — not a listing of all possible answers. Of course, if you had merely wanted a random answer, you could have picked one yourself, with much less trouble. </p>
</blockquote>

<p>yet the metaphor of a quantum computer processing answers in parallel is widespread &amp; a reasonable conceptual simplification of QM computing, and referred to in many QM computing textbooks. there are probably other examples from QM theory/computing. </p>

<p>there is a natural tension in TCS and other theoretical research in communicating with the public/media because it sometimes tends to emphasize critical distinctions/concepts as part of rigorous training that are not known or crucial to laymen. in other words in many cases research theory works against various conceptual "big picture" simplifications that are legitimate to laymen.</p>

CC BY-SA 3.0
2012-07-11T18:58:32.857Z
You need to put your answer in the right format :). But I actually don't think your answer is appropriate. Because the "quantum computer can try all cases in parallel" argument is wrong in important ways, and is not helpful as intuition. So I don't think there's a higher "moral truth"
Suresh Venkat
CC BY-SA 3.0
2012-07-11T19:01:59.007Z
I agree with @SureshVenkat a quantum computer processing all possibilities in parallel is about as close to the moral truth as a probabilistic computer processing all possibilities in parallel. It is completely useless for intuition and there is no "kind of true" thing it is approximating.
Artem Kaznatcheev
CC BY-SA 3.0
2012-07-11T19:14:48.250Z
When I run across people who insist that QC's can solve all possible inputs to a problem, I usually respond with: "OK, fine. You get *one* answer. At random. How do you ensure that it's probably the right one?"
Josephine Moeller
CC BY-SA 3.0
2012-07-11T23:48:28.947Z
@ArtemKAznatcheev: I would definitely say there’s something meaningful in this simplification.  In a quantum computation (unlike a probabilistic one), components of the state corresponding to different possibilities can (through further linear operations) cancel out, or otherwise “interfere”.  I’d agree this intuition doesn’t go very far towards what’s really going on, but it does go a little way, and I’ve yet to see any way of going further without getting into the actual linear algebra, which for most lay readers would be a complete turnoff.
PLL
CC BY-SA 3.0
2012-07-11T23:55:29.950Z
I guess I’d phrase it as something like “You can imagine, very roughly, that a quantum computer can run many different versions of a computation at once, and then combine the results of them all into a single output.  The magic of many quantum algorithms lies in finding the right superposition of possibilities to start with, and the right clever way to combine the outputs at the end, so that the wrong possibilities all cancel out (or very nearly), and the correct possibility is the one remaining.”  (Specifically, I think this is a fair gloss of Grover search and many algorithms based on it.)
PLL
CC BY-SA 3.0
2012-07-12T11:28:01.057Z
@PLL: in a nondeterministic machine, the branches don't interfere either. So while we suspect that BQP is strictly larger than BPP, this makes comparing a quantum computer to a nondeterministic Turing machine exactly the wrong sort of comparison to make. You could try to make a (still quite sloppy) comparison to Parity-P or Gap-P, but somehow I don't think that this will at all help you to convey what quantum computers do very much.
Niel de Beaudrap
CC BY-SA 3.0
2012-07-14T16:20:48.753Z
NdB-- PLL said nothing about nondeterminism. actually this is another question about how nondeterminism relates to parallelism. they are similar, but not the same. and is everyone getting hung up on the word "answer" I quoted? to me its more about parallelism. Im sure theres a theoretically sound way of viewing QM computation as parallel classical computation no matter what the result of open complexity class separations (classical vs QM etc) turn out to be. am disappointed that nobody on this normally high brainpower site picked up on this. may reformulate this as a new question later....
vzn
CC BY-SA 3.0
2012-07-16T16:22:28.553Z
related -- [viewing QM computing as classical parallel computation](http://cstheory.stackexchange.com/questions/12033/is-there-a-valid-way-of-viewing-qm-computing-as-parallel-classical-computation)
vzn
CC BY-SA 3.0
2012-07-18T10:36:13.727Z
@vzn: what PLL argued was that nondeterministic Turing machines were a more useful simplification than probabilistic machines; I just pointed out that the 'shortcoming' of probabilistic machines that he pointed out is something that probabilistic machines have in common with nondeterministic ones. (And incidentally: if you don't use full usernames, the users don't get notified that you've responded.)
Niel de Beaudrap
CC BY-SA 3.0
2012-07-11T18:41:00.063Z
2012-07-11T18:56:56.297Z
2012-07-11T18:56:56.297Z
vzn
<p>Larry Wasserman has a recent post where he talks about the "p-value police". He makes an interesting point (all emphasis mine) (the premise in italics that I added, and his response below it):</p>

<blockquote>
  <p><em>The most common complaint is that physicists and journalists explain
  the meaning of a p-value incorrectly. For example, if the p-value is
  0.000001 then we will see statements like “there is a 99.9999% confidence that the signal is real.” We then feel compelled to correct
  the statement: if there is no effect, then the chance of something as
  or more extreme is 0.000001.</em></p>
  
  <p>Fair enough. But does it really matter? The big picture is: the
  evidence for the effect is overwhelming. Does it really matter if the
  wording is a bit misleading? <strong>I think we reinforce our image as pedants
  if we complain about this.</strong></p>
</blockquote>

<p>Which got me thinking - </p>

<blockquote>
  <p>Are there good examples of pedantry in TCS ? Such an example would
  consist of </p>
  
  <ul>
  <li>A claim that is commonly made in the popular press</li>
  <li>A standard correction that people insist on making</li>
  <li>The correct "big picture" that the claim does capture even while being imprecise.</li>
  </ul>
  
  <p>where the claim is mathemtically wrong  but "morally right" and the
  correction is technically correct but doesn't change the intuitive
  understanding.</p>
</blockquote>

<p>To lead things off, my example would be:</p>

<ul>
<li>Claim - NP-complete problems take exponential time to solve</li>
<li>Correction - No in fact we just don't know if they can be solved in polynomial time</li>
<li>Big picture - NP-complete problems are HARD</li>
</ul>

<p>Caution: I know there are many on this forum whose head will explode at the idea of claims that are wrong but "morally correct" :). Remember that these are statements targeted towards the public (where some degree of license can be permitted), rather than statements made in a research paper. </p>

CC BY-SA 3.0
2012-07-11T16:51:32.173Z
Not sure about this, but might "true randomness" qualify? People might often claim that something is (truly) random, when in fact we don't know. Since $K(x)$ of a string $x$ is uncomputable, we can't verify the claim of randomness. Nevertheless, many sources of generating randomness are often random enough in practice.
Juho
CC BY-SA 3.0
2012-07-11T16:53:15.373Z
It's an interesting idea, but is there much talk about true randomness in the popular press ?
Suresh Venkat
CC BY-SA 3.0
2012-07-11T17:02:36.170Z
I guess that's a bit subjective -- maybe as much as the popular press talks about NP-completeness? But yes, I guess randomness comes up in different contexts, but usually there is no distinction made between pseudorandomness and (true) randomness.
Juho
<ds.algorithms><soft-question><big-list>
Examples of pedantry in TCS
Suresh Venkat
# Examples of pedantry in TCS

(Asked by: username_0 on 2012-07-11)

Larry Wasserman has a recent post where he talks about the "p-value police". He makes an interesting point (all emphasis mine) (the premise in italics that I added, and his response below it):

> *The most common complaint is that physicists and journalists explain
> the meaning of a p-value incorrectly. For example, if the p-value is
> 0.000001 then we will see statements like “there is a 99.9999% confidence that the signal is real.” We then feel compelled to correct
> the statement: if there is no effect, then the chance of something as
> or more extreme is 0.000001.*
>
> Fair enough. But does it really matter? The big picture is: the
> evidence for the effect is overwhelming. Does it really matter if the
> wording is a bit misleading? **I think we reinforce our image as pedants
> if we complain about this.**

Which got me thinking -

> Are there good examples of pedantry in TCS ? Such an example would
> consist of
>
> * A claim that is commonly made in the popular press
> * A standard correction that people insist on making
> * The correct "big picture" that the claim does capture even while being imprecise.
>
> where the claim is mathemtically wrong but "morally right" and the
> correction is technically correct but doesn't change the intuitive
> understanding.

To lead things off, my example would be:

* Claim - NP-complete problems take exponential time to solve
* Correction - No in fact we just don't know if they can be solved in polynomial time
* Big picture - NP-complete problems are HARD

Caution: I know there are many on this forum whose head will explode at the idea of claims that are wrong but "morally correct" :). Remember that these are statements targeted towards the public (where some degree of license can be permitted), rather than statements made in a research paper.

**Tags:** ds.algorithms, soft-question, big-list
> **Comments:**
> **username_1**: Not sure about this, but might "true randomness" qualify? People might often claim that something is (truly) random, when in fact we don't know. Since $K(x)$ of a string $x$ is uncomputable, we can't verify the claim of randomness. Nevertheless, many sources of generating randomness are often random enough in practice.  
> **username_0**: It's an interesting idea, but is there much talk about true randomness in the popular press ?  
> **username_1**: I guess that's a bit subjective -- maybe as much as the popular press talks about NP-completeness? But yes, I guess randomness comes up in different contexts, but usually there is no distinction made between pseudorandomness and (true) randomness.  

---

## 5 answers

### Answer by username_2 on 2012-07-11. Score: 17

Hm, its tough even to think of examples of claims about TCS that make it to the popular press.

One thing I have seen occasionally is the claim that factoring is NP-hard, when explaining cryptography. This is related to the less innocuous error of claiming that quantum computers can solve NP hard problems, but restricted to the context of cryptography, this is a relatively mild error. The point is just that we (users of cryptography) seem to believe that there is no efficient algorithm for solving the problem. The particular conjectures we use to justify this assertion are besides the point.


---

### Answer by username_3 on 2012-07-11. Score: 12

* claim by press: about things that grow "exponentially" ie claim of O(k^n)
* actually true: often, a constant power O(n^k)
* big picture: it grows fast enough, all right

> **Comments:**
> **username_0**: That's a nice one. I was thinking about that as well.  
> **username_4**: I actually keep one of these on my webpage: http://cg.scs.carleton.ca/~morin/misc/nortel/  
> **username_0**: Except in that case it DID make a difference :)  
> **username_5**: exponential has taken the meaning of anything  that grows superlinearly  
> **username_6**: The word _"exponential"_ is one of the most abused. Here are some examples I've seen: _"The number of goals scored by [some soccer player] has been growing exponentially from each season to the next"_,_"I've been able to improve my team working attitude in an exponential manner along the years"_,_"The number of channels available through satellite TV is exponential"_.  

---

### Answer by username_7 on 2012-07-14. Score: 12

* Claim by press: First polynomial time algorithm for an important practical problem will necessarily change our lives, will be the next best thing after sliced bread, etc.

For examples, take any press article about the ellipsoid algorithm from the time it was discovered (great account of the story: <http://www.springerlink.com/content/vh32532p5048062u/>). The press claimed that this new great mathematical discovery will affect everyone's lives, solve TSP (which they found especially ironic given how few traveling salesmen there were in the USSR!), turn crypto upside down, etc.

Then there is AKS, which in some reports was even implied to solve factoring..or at least to be an industry-changing innovation.

I am sure there are plenty more examples.

* Actually true: Polynomial time does not mean practical! Case in point: ellipsoid algorithm, sampling from high-dimensional convex bodies. Worst-case exponential time does not mean impractical. Case in point: simplex algorithm. When the new algorithm is merely the first deterministic polytime algorithm for a problem, this has even less relevance to practice.
* Big picture: these results are breakthroughs, and at least the press gets people excited about them, even if it is for the wrong reasons. And much of the time a polynomial time algorithm eventually turns into a reasonably efficient algorithm. For example Gentry's homomorphic encryption scheme is not practical yet, but its running time has been improved significantly. Near-linear time solvers for SDD systems of equations seem to be well on the way to practicality but started off with a $\log^5 n$ factor hidden in the soft-oh notation.


---

### Answer by username_8 on 2012-07-13. Score: 6

The popular press often gives the impression that the primary, if not the only, reason that computers are succeeding at more and more tasks (beating Kasparov at chess, beating Jennings at Jeopardy, etc.) is increased raw processing power. Algorithmic advances are typically not given that much credit.

However, I'm ambivalent about whether insisting that algorithmic advances be given more weight is "pedantry." On the one hand, I think that those of us who are more theoretically inclined can sometimes overstate the importance of algorithmic advances and only grudgingly admit the importance of increased processing power. On the other hand, I do think the public should be better informed about the role of theoretical advances in solving practical problems.

> **Comments:**
> **username_9**: I think it could be argued that "pedantry" is accurate.  Many people don't know the difference between hardware or software (really a surprising amount for me at least).  To the uninitiated, where exactly the improvement comes from could be classified as pedantry, even though we know that there are huge structural and conceptual differences.  

---

### Answer by username_10 on 2012-07-11. Score: -8

Scott Aaronson, while a foremost authority, seems to regularly take the media to task for not hairsplitting accurately. eg his recent column in the NYT article ["Quantum Computing Promises New Insights, Not Just Supermachines"](http://www.nytimes.com/2011/12/06/science/scott-aaronson-quantum-computing-promises-new-insights.html) [italics added]

> Struggling to shoehorn that mathematics into newspaper-friendly metaphors, *most popular writers describe a quantum computer as a magic machine that could process every possible answer in parallel,* rather than trying them one at a time. Supposedly, it could do that because, unlike today’s computers that manipulate bits, a quantum computer would manipulate quantum bits, or qubits, which can be 0 and 1 simultaneously.
>
> But that’s a crude way to visualize what a quantum computer does, and misses the most important part of the story. When you measure a quantum computer’s output, you see just a single, random answer — not a listing of all possible answers. Of course, if you had merely wanted a random answer, you could have picked one yourself, with much less trouble.

yet the metaphor of a quantum computer processing answers in parallel is widespread & a reasonable conceptual simplification of QM computing, and referred to in many QM computing textbooks. there are probably other examples from QM theory/computing.

there is a natural tension in TCS and other theoretical research in communicating with the public/media because it sometimes tends to emphasize critical distinctions/concepts as part of rigorous training that are not known or crucial to laymen. in other words in many cases research theory works against various conceptual "big picture" simplifications that are legitimate to laymen.

> **Comments:**
> **username_0**: You need to put your answer in the right format :). But I actually don't think your answer is appropriate. Because the "quantum computer can try all cases in parallel" argument is wrong in important ways, and is not helpful as intuition. So I don't think there's a higher "moral truth"  
> **username_11**: I agree with @SureshVenkat a quantum computer processing all possibilities in parallel is about as close to the moral truth as a probabilistic computer processing all possibilities in parallel. It is completely useless for intuition and there is no "kind of true" thing it is approximating.  
> **username_12**: When I run across people who insist that QC's can solve all possible inputs to a problem, I usually respond with: "OK, fine. You get *one* answer. At random. How do you ensure that it's probably the right one?"  
> **username_13**: @ArtemKAznatcheev: I would definitely say there’s something meaningful in this simplification.  In a quantum computation (unlike a probabilistic one), components of the state corresponding to different possibilities can (through further linear operations) cancel out, or otherwise “interfere”.  I’d agree this intuition doesn’t go very far towards what’s really going on, but it does go a little way, and I’ve yet to see any way of going further without getting into the actual linear algebra, which for most lay readers would be a complete turnoff.  
> **username_13**: I guess I’d phrase it as something like “You can imagine, very roughly, that a quantum computer can run many different versions of a computation at once, and then combine the results of them all into a single output.  The magic of many quantum algorithms lies in finding the right superposition of possibilities to start with, and the right clever way to combine the outputs at the end, so that the wrong possibilities all cancel out (or very nearly), and the correct possibility is the one remaining.”  (Specifically, I think this is a fair gloss of Grover search and many algorithms based on it.)  
> **username_14**: @PLL: in a nondeterministic machine, the branches don't interfere either. So while we suspect that BQP is strictly larger than BPP, this makes comparing a quantum computer to a nondeterministic Turing machine exactly the wrong sort of comparison to make. You could try to make a (still quite sloppy) comparison to Parity-P or Gap-P, but somehow I don't think that this will at all help you to convey what quantum computers do very much.  
> **username_10**: NdB-- PLL said nothing about nondeterminism. actually this is another question about how nondeterminism relates to parallelism. they are similar, but not the same. and is everyone getting hung up on the word "answer" I quoted? to me its more about parallelism. Im sure theres a theoretically sound way of viewing QM computation as parallel classical computation no matter what the result of open complexity class separations (classical vs QM etc) turn out to be. am disappointed that nobody on this normally high brainpower site picked up on this. may reformulate this as a new question later....  
> **username_10**: related -- [viewing QM computing as classical parallel computation](http://cstheory.stackexchange.com/questions/12033/is-there-a-valid-way-of-viewing-qm-computing-as-parallel-classical-computation)  
> **username_14**: @vzn: what PLL argued was that nondeterministic Turing machines were a more useful simplification than probabilistic machines; I just pointed out that the 'shortcoming' of probabilistic machines that he pointed out is something that probabilistic machines have in common with nondeterministic ones. (And incidentally: if you don't use full usernames, the users don't get notified that you've responded.)  

---

