<p>One idea is something simple from <strong>streaming algorithms</strong>. Probably the best candidate is the majority algorithm. Say you see a stream of numbers $s_1, \ldots, s_n$, one after the other, and you know one number occurs more than half the time, but you don't know which one. How can you find the majority number if you can only remember <em>two numbers at a time</em>? The answer is the Misra-Gries algorithm.</p>

<p>At each time step you store a number $x$ from the stream and a frequency counter $f$. At the start you set $x$ to the first number of the stream and initialize the frequency $f$ to 1. Then whenever you see a new number $s_i$, you check if $x = s_i$. If $x=s_i$, increase $f$ to $f+1$, otherwise decrease $f$ to $f-1$. If $f=0$, set $x$ to $s_i$ and $f$ back to $1$. After the last element of the stream, if there was a majority element, it will be equal to $x$.</p>

<p>Another idea is the well-known game to illustrate <strong>zero knowledge proofs</strong>. I think it's due to <a href="http://www.wisdom.weizmann.ac.il/~/oded/poster03.html">Oded Goldreich</a> and is similar to the zero knowledge proof for graph isomorphism.</p>

<p>To make the answer self-contained, here is the game. Suppose you want to convince your color-blind friend that you can tell red from green. Your friend has two decks of cards, and he knows one pile is green and the other is red. He does the following without you seeing him: with probability 1/2 he draws one card from each deck, with probability 1/4 he draws two cards from the left deck, and with probability 1/4 he draws two cards from the right deck. Then he shows you the cards and asks you if they are the same color. If you are not color blind, you can of course answer correctly every time. If you are color blind, you will fail with probability 1/2. So now if the game is played 10 times, the probability that you can win every time while being color blind is extremely low.</p>

<p>The kicker is that if your friend knew the two decks of cards are two different colors, but did not know which one is red and which green, he still will not know at the end of this! So in summary:</p>

<ol>
<li>There is place for randomness in proofs.</li>
<li>You can convince someone you know something without giving them any information about it.</li>
</ol>

CC BY-SA 3.0
2015-05-26T19:16:50.747Z
Besides Misra-Gries, I also think [reservoir sampling](http://en.wikipedia.org/wiki/Reservoir_sampling) is simple but nice.
Juho
CC BY-SA 3.0
2015-05-26T20:42:44.823Z
@Juho I agree. A popular interview question to boot :).
Sasho Nikolov
CC BY-SA 3.0
2015-05-26T18:58:12.010Z
2015-05-26T18:58:12.010Z
Sasho Nikolov
<p>For a general audience you have to stick to things that they can <em>see</em>. As soon as you start theorizing they'll start up their mobile phones.</p>

<p>Here are some ideas which could be worked out to complete examples:</p>

<ol>
<li>There is a surface which <a href="https://en.wikipedia.org/wiki/Mobius_strip">has only one side</a>.</li>
<li>A curve may <a href="https://en.wikipedia.org/wiki/Space_filling_curve">fill an entire square</a>.</li>
<li>There are <a href="https://en.wikipedia.org/wiki/Curve_of_constant_width">constant width curves</a> other than a circle.</li>
<li>It is possible to color the plane with three colors in such a way that <a href="https://en.wikipedia.org/wiki/Newton_fractal">every border point is a tri-border</a>.</li>
</ol>

<p>If you can rely on a bit of mathematical knowledge, you can do more:</p>

<ol>
<li>There are as many odd numbers as there are natural numbers.</li>
<li>There is a <a href="https://en.wikipedia.org/wiki/Weierstrass_function">continuous and nowhere differentiable function</a>.</li>
<li>There is a function $f : \mathbb{R} \to \mathbb{R}$ which is discontinuous at all rational numbers and differentiable at all irrational numbers.</li>
<li>The <a href="https://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox">Banach-Tarski "paradox"</a>.</li>
</ol>

<p>For programmers you can try:</p>

<ol>
<li><p>The <a href="http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/">impossible functionals</a>: there is a program which takes a predicate <code>p : stream → bool</code>, where <code>stream</code> is the datatype of infinite binary sequences, and returns <code>true</code> if and only if <code>p α</code> is <code>true</code> for <em>all</em> streams <code>α</code> (that's uncountably many), and <code>false</code> otherwise.</p></li>
<li><p>It is possible to <a href="http://www.math.stonybrook.edu/~scott/blair/How_play_poker.html">play poker by telephone</a> in a trusted way which prevents cheating.</p></li>
<li><p>A group of people can calculate their average salary without anybody finding out any other person's salary.</p></li>
<li><p>There is a program which <a href="http://math.andrej.com/2006/04/25/konigs-lemma-and-the-kleene-tree/">constructs a <em>binary</em> tree $T$</a> with the following properties:</p>

<ul>
<li>the tree $T$ is infinite</li>
<li>there is no program that traces an infinite path in $T$</li>
</ul></li>
</ol>

CC BY-SA 3.0
2015-06-03T00:34:18.003Z
the banach-tarski paradox (and related paradoxes) have to do with notions (and manipulations) of infinity, something that even professional mathematicians can get wrong (or disagree a lot about it) :)
Nikos M.
CC BY-SA 3.0
2015-06-03T12:10:21.807Z
Agreed, but it's the sort of ourageous theorem that sparks people's interest. It gives them a jolt and makes them doubt their own intuitions about infinity.
Andrej Bauer
CC BY-SA 3.0
2015-05-26T17:58:17.960Z
2015-05-26T18:18:43.450Z
2015-05-26T18:18:43.450Z
Andrej Bauer
<p>The volume of a unit sphere of dimension $n$ first grows as $n$ grows ($2,\pi,4\pi/3,\dots$) but starts decreasing for $n=6$ and eventually converges to $0$ as $n\to\infty$.</p>

CC BY-SA 3.0
2015-10-16T17:03:40.990Z
There are many related fun, counterintuitive facts about geometry in high dimensions. For example, take the unit hypercube and inscribe a sphere touching all the sides. How far is a corner of the hypercube from the sphere? (Answer: It diverges to $\infty$ as the dimension grows. The radius of the sphere is $0.5$, but the distance from center to corner of the cube is $0.5\sqrt{n}$.)
usul
CC BY-SA 3.0
2015-06-07T10:38:04.933Z
And the reason for this is the arbitrary decision to consider spheres of unit radius, as opposed to another length parameter. In particular, the volumes of spheres of diameter 1 are decreasing from the get-go.
Emil Jeřábek
CC BY-SA 3.0
2015-05-27T13:49:27.297Z
2015-05-27T13:49:27.297Z
Denis
<p>One thing that proves to be counterintuitive for CS undergraduates, is the fact that one can select the $i$-th order statistics from an unsorted array of $n$ elements in $O(n)$ time. All of the students think they must first necessarily sort the array (in $O(n~lg ~n)$ time).</p>

CC BY-SA 3.0
2015-05-30T09:13:45.030Z
2015-05-30T09:13:45.030Z
Massimo Cafaro
<p>A counter intuitive result from complexity theory is the PCP theorem:</p>

<p>Informally, states that for every $NP$ problem $A$, there is an efficient randomized Turing machine that can verify proof correctness (proof of membership in $A$) using logarithmic number of random bits and reading only constant number of bits from the proof. The constant can be reduced to 3 bits. Therefore, the randomized verifier needs to read only three bits from the proclaimed proof.</p>

CC BY-SA 3.0
2015-05-28T01:37:24.433Z
What is the reference for "can be reduced to 3 bits"?
Ryan Dougherty
CC BY-SA 3.0
2015-05-28T08:30:48.363Z
That is known as Håstad's 3 bit (or 3 query) PCP theorem, and it requires sacrificing perfect completeness
Joe Bebel
CC BY-SA 3.0
2015-05-28T09:20:07.957Z
Here you find further information and the reference to  Håstad's paper: http://people.csail.mit.edu/madhu/papers/1998/glst.pdf
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-05-28T18:18:22.937Z
@JoeBebel Actually there are 3-bit verifiers with perfect completeness. Hastad's verifier is "linear": it samples three bits and takes their XOR. For such a verifier you do need to sacrifice perfect completeness. BTW, there are PCP proofs that read only two bits (again necessarily without perfect completeness). For example see my answer here http://cstheory.stackexchange.com/a/20549/4896
Sasho Nikolov
CC BY-SA 3.0
2015-05-27T10:19:48.287Z
2015-05-27T10:40:44.370Z
2015-05-27T10:40:44.370Z
Mohammad Al-Turkistany
<p>building on MdBs answer/ angle, a classic result of something counterintuitive <em>at the time of discovery</em> in TCS at its foundations is the existence of <a href="http://en.wikipedia.org/wiki/Undecidable_problem">(un)decidability</a> itself. at the turn of the 20<sup>th</sup> century Hilbert, mirroring the thinking of other leading mathematicians of the time, thought that mathematics could be <em>systematized</em> (somewhat in the form of what we now recognize as <em>algorithmic</em>) &amp; somewhat via the concept of <a href="http://en.wikipedia.org/wiki/Finitism">"finitism"</a> (which has rough parallels to the idea of an algorithm as a finite sequence of steps). he proposed famous open problems along these lines. his (and others) intuition turned out to be wrong in a sort of spectacular way. the counterproof is <a href="http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems">Godels theorem</a> and <a href="http://en.wikipedia.org/wiki/Halting_problem">Turings Halting problem</a>. both were initially extremely abstract concepts/ results and long, highly technical papers/ arguments only understandable to leading mathematicians of the time, but now are refined to simpler conceptual structures and taught to undergraduates. these were not initially seen as two aspects/face of the same phenomenon but now they are. </p>

<p>also it took close to ~¾ of a century to prove that integer Diophantine equations are undecidable, <a href="http://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem">Hilberts 10th problem</a>. this is counterintuitive in the sense that it was always known that number theory was extremely <em>difficult</em> but the concept that some specific/ identifiable problems in it may actually be <em>"impossible to resolve"</em> was nearly shocking at the time to some. undecidability continues to be a deep challenge in math/ TCS even as we have decades of exponential increases in hardware due to Moores law and yet massive supercomputers that are in a sense still "powerless against it". some aspects of the surprise of undecidability can be found in the book <a href="http://rads.stackoverflow.com/amzn/click/0195030850">Mathematics, Loss of Certainty</a> by Klein.</p>

CC BY-SA 3.0
2015-05-30T15:03:10.357Z
Turing's paper was _not_ extremely abstract/technical. It's actually quite straightforward and accessible.
Jeffε
CC BY-SA 3.0
2015-05-30T18:49:07.917Z
fine, maybe for _you, now,_ but how many _undergraduates_ do you know who can follow the _entire_ paper? did _you_ follow it as an undergraduate? why are the _full actual contents_ not covered in undergrad classes? why has an _[entire book](http://www.amazon.com/The-Annotated-Turing-Historic-Computability/dp/0470229055)_ been written analyzing that single paper? what about parts that anticipate concepts not discovered until _decades later_ such as _curry-howard_ correspondence, high level programming languages, etc?
vzn
CC BY-SA 3.0
2015-05-30T19:15:47.627Z
Still, "long, highly technical papers/ arguments only understandable to leading mathematicians of the time" is not accurate wrt Turing's paper, which is orders of magnitude more accessible than Godel's papers. This answer is full of non-sequitirs. I cannot see what finitism has to do with Hilbert's program (I am certain he would not have been a finitist). What Moore's law has to do with undecidability is also a puzzle to me. Would you really expect exponentially faster hardware would solve *undecidable* problems?
Sasho Nikolov
CC BY-SA 3.0
2015-05-30T19:31:11.180Z
_lol_ Hilbert was involved in _inventing/ originating_ the concept of finitism. agreed the short answer could be "filled out" further. more details in [chat] for anyone _openminded_ / willing to _listen_
vzn
CC BY-SA 3.0
2015-05-30T19:40:40.360Z
_why are the full actual contents not covered in undergrad classes?_ — Not enough time.
Jeffε
CC BY-SA 3.0
2015-05-31T04:40:35.077Z
Fair enough, I did not know about Hilbert's finitism. I was only familiar with modern and much stricter notions of finitism. It would be better if you wrote a good answer rather than refer people to chat, but I somehow doubt you'd follow this advice.
Sasho Nikolov
CC BY-SA 3.0
2015-05-26T23:05:47.443Z
2015-05-26T23:05:47.443Z
vzn
<p>It seems obvious, but from personal experience, the idea that you can estimate the median of a collection of items using a constant number of operations is a little shocking. And if that seems a little too technical, you can always convert it into a statement about polls an elections (you need 1300 people to get a sample with 3% error, regardless of the population size). </p>

<p>Related to this is the <a href="https://en.wikipedia.org/wiki/Birthday_problem" rel="noreferrer">birthday paradox</a> of course. </p>

CC BY-SA 3.0
2015-10-16T04:36:24.347Z
2015-10-16T04:36:24.347Z
Suresh Venkat
<p>Perhaps a good example (not directly related to computational complexity) is the Turing universality of simple computational models.</p>

<p>For example the <a href="http://en.wikipedia.org/wiki/Rule_110" rel="noreferrer">rule 110</a> is efficiently (weakly) universal:</p>

<p>Given an (infinite) array of 0-1 (white-black) cells properly initialized and the simple substitution rules:</p>

<p><img src="https://i.sstatic.net/3EGbX.png" alt="enter image description here"></p>

<p>we have a "working computer"! :-)</p>

<p>For the definition of "weakly" and "efficient", and for other examples of simple universal Turing machines look at: <a href="http://arxiv.org/abs/1110.2230" rel="noreferrer">Turlough Neary, Damien Woods; The complexity of small universal Turing machines: a survey</a>. </p>

<p>Another puzzling example is the Turing completeness of the <a href="http://en.wikipedia.org/wiki/FRACTRAN" rel="noreferrer">FRACTRAN</a> "programming language":</p>

<ul>
<li>the "program" is a list of fractions: $(p_1/q_1, p_2/q_2,..., p_n/q_n)$;</li>
<li>given an input $n$ find the first $q_i$ that divides $n$ and replace $n \leftarrow n \cdot \frac{p_i}{q_i}$;</li>
<li>repeat the previous step until no $q_i$ divides $n$.</li>
</ul>

<p>With a suitable encoding of the input $n$, FRACTRAN can simulate any Turing machine.</p>

<p>You can also use other models, like cyclic tag systems, ant-automata, ....<br>The not-so-intuitive idea is that "computation" is hidden almost everywhere ... Wolfram wrote 1192 pages filled with figures and text to better express that idea in his <a href="https://www.wolframscience.com/nksonline/toc.html" rel="noreferrer">A New Kind of Science</a> (yes... yes... despite some critical reviews I finally bought a hard-copy of it :-) </p>

CC BY-SA 3.0
2015-05-26T10:24:30.603Z
2015-05-26T18:34:52.307Z
2015-05-26T18:34:52.307Z
Marzio De Biasi
<p>A few good candidates off the top of my head:</p>

<ul>
<li><p>Every NFA has an equivalent DFA</p></li>
<li><p>There exists a finite field of size $p$ or $p^i$ where $i \in \mathbb{N}$ and $i &gt; 0$.</p></li>
<li><p>Public key cryptography</p>

<ul>
<li><p>Calling to a function with encrypted arguments and receiving the desired result without revealing information about your inputs</p></li>
<li><p>RSA encrpytion</p></li>
</ul></li>
<li><p>Reed-Solomon codes</p></li>
<li><p>Countability</p>

<ul>
<li><p>$|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{N} \times \mathbb{N}| = |\mathbb{Q}|$</p></li>
<li><p>The set of elements in the language $\{0,1\}^*$ is countable, but $\mathbb{R}$ is uncountable (Cantor's diagonalization)</p></li>
<li><p>Cantor's Theorem: $|S| &lt; |\mathcal{P}(S)|$</p></li>
</ul></li>
<li><p>On a more philosophical level, it astonished me that Turing machines accurately define computation</p></li>
</ul>

CC BY-SA 3.0
2015-06-06T23:05:00.020Z
2015-06-06T23:05:00.020Z
Bharadwaj Ramachandran
<p>I am looking for examples of results which go against people's intuition for a general audience talk. Results which if asked from non-experts "what does your intuition tell you?", almost all would get it wrong. Results' statement should be easily explainable to undergraduates in cs/math. I am mainly looking for results in computer science.</p>

<p>What are the most counterintuitive/unexpected results (of general interest) in your area?</p>

CC BY-SA 3.0
2015-05-26T03:40:59.093Z
closely related: http://cstheory.stackexchange.com/q/276/4896 and http://cstheory.stackexchange.com/q/2802/4896
Sasho Nikolov
CC BY-SA 3.0
2015-05-26T05:00:30.897Z
The second of Sasho's links is a duplicate, no?
Huck Bennett
CC BY-SA 3.0
2015-05-26T08:11:33.370Z
Similar but not the same. I am looking for results which are interesting and counterintuitive for general cs/math undergraduates not researchers. E.g. IP=PSPACE would not be a good answer.
Anonymous
CC BY-SA 3.0
2015-05-28T01:36:28.527Z
Is there a specific field you are looking for or just a general (theory) answer?
Ryan Dougherty
<big-list><teaching><intuition>
Counterintuitive results for undergraduates
Anonymous
# Counterintuitive results for undergraduates

(Asked by: username_0 on 2015-05-26)

I am looking for examples of results which go against people's intuition for a general audience talk. Results which if asked from non-experts "what does your intuition tell you?", almost all would get it wrong. Results' statement should be easily explainable to undergraduates in cs/math. I am mainly looking for results in computer science.

What are the most counterintuitive/unexpected results (of general interest) in your area?

**Tags:** big-list, teaching, intuition

> **Comments:**
> **username_1**: closely related: http://cstheory.stackexchange.com/q/276/4896 and http://cstheory.stackexchange.com/q/2802/4896  
> **username_2**: The second of Sasho's links is a duplicate, no?  
> **username_0**: Similar but not the same. I am looking for results which are interesting and counterintuitive for general cs/math undergraduates not researchers. E.g. IP=PSPACE would not be a good answer.  
> **username_3**: Is there a specific field you are looking for or just a general (theory) answer?  

---

## 9 answers

### Answer by username_5 on 2015-05-26. Score: 25

For a general audience you have to stick to things that they can *see*. As soon as you start theorizing they'll start up their mobile phones.

Here are some ideas which could be worked out to complete examples:

1. There is a surface which [has only one side](https://en.wikipedia.org/wiki/Mobius_strip).
2. A curve may [fill an entire square](https://en.wikipedia.org/wiki/Space_filling_curve).
3. There are [constant width curves](https://en.wikipedia.org/wiki/Curve_of_constant_width) other than a circle.
4. It is possible to color the plane with three colors in such a way that [every border point is a tri-border](https://en.wikipedia.org/wiki/Newton_fractal).

If you can rely on a bit of mathematical knowledge, you can do more:

1. There are as many odd numbers as there are natural numbers.
2. There is a [continuous and nowhere differentiable function](https://en.wikipedia.org/wiki/Weierstrass_function).
3. There is a function $f : \mathbb{R} \to \mathbb{R}$ which is discontinuous at all rational numbers and differentiable at all irrational numbers.
4. The [Banach-Tarski "paradox"](https://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox).

For programmers you can try:

1. The [impossible functionals](http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/): there is a program which takes a predicate `p : stream → bool`, where `stream` is the datatype of infinite binary sequences, and returns `true` if and only if `p α` is `true` for *all* streams `α` (that's uncountably many), and `false` otherwise.
2. It is possible to [play poker by telephone](http://www.math.stonybrook.edu/~scott/blair/How_play_poker.html) in a trusted way which prevents cheating.
3. A group of people can calculate their average salary without anybody finding out any other person's salary.
4. There is a program which [constructs a *binary* tree $T$](http://math.andrej.com/2006/04/25/konigs-lemma-and-the-kleene-tree/) with the following properties:

   * the tree $T$ is infinite
   * there is no program that traces an infinite path in $T$

> **Comments:**
> **username_6**: the banach-tarski paradox (and related paradoxes) have to do with notions (and manipulations) of infinity, something that even professional mathematicians can get wrong (or disagree a lot about it) :)  
> **username_5**: Agreed, but it's the sort of ourageous theorem that sparks people's interest. It gives them a jolt and makes them doubt their own intuitions about infinity.  

---

### Answer by username_1 on 2015-05-26. Score: 17

One idea is something simple from **streaming algorithms**. Probably the best candidate is the majority algorithm. Say you see a stream of numbers $s\_1, \ldots, s\_n$, one after the other, and you know one number occurs more than half the time, but you don't know which one. How can you find the majority number if you can only remember *two numbers at a time*? The answer is the Misra-Gries algorithm.

At each time step you store a number $x$ from the stream and a frequency counter $f$. At the start you set $x$ to the first number of the stream and initialize the frequency $f$ to 1. Then whenever you see a new number $s\_i$, you check if $x = s\_i$. If $x=s\_i$, increase $f$ to $f+1$, otherwise decrease $f$ to $f-1$. If $f=0$, set $x$ to $s\_i$ and $f$ back to $1$. After the last element of the stream, if there was a majority element, it will be equal to $x$.

Another idea is the well-known game to illustrate **zero knowledge proofs**. I think it's due to [Oded Goldreich](http://www.wisdom.weizmann.ac.il/~/oded/poster03.html) and is similar to the zero knowledge proof for graph isomorphism.

To make the answer self-contained, here is the game. Suppose you want to convince your color-blind friend that you can tell red from green. Your friend has two decks of cards, and he knows one pile is green and the other is red. He does the following without you seeing him: with probability 1/2 he draws one card from each deck, with probability 1/4 he draws two cards from the left deck, and with probability 1/4 he draws two cards from the right deck. Then he shows you the cards and asks you if they are the same color. If you are not color blind, you can of course answer correctly every time. If you are color blind, you will fail with probability 1/2. So now if the game is played 10 times, the probability that you can win every time while being color blind is extremely low.

The kicker is that if your friend knew the two decks of cards are two different colors, but did not know which one is red and which green, he still will not know at the end of this! So in summary:

1. There is place for randomness in proofs.
2. You can convince someone you know something without giving them any information about it.

> **Comments:**
> **username_4**: Besides Misra-Gries, I also think [reservoir sampling](http://en.wikipedia.org/wiki/Reservoir_sampling) is simple but nice.  
> **username_1**: @username_4 I agree. A popular interview question to boot :).  

---

### Answer by username_7 on 2015-05-27. Score: 13

The volume of a unit sphere of dimension $n$ first grows as $n$ grows ($2,\pi,4\pi/3,\dots$) but starts decreasing for $n=6$ and eventually converges to $0$ as $n\to\infty$.

> **Comments:**
> **username_9**: And the reason for this is the arbitrary decision to consider spheres of unit radius, as opposed to another length parameter. In particular, the volumes of spheres of diameter 1 are decreasing from the get-go.  
> **username_8**: There are many related fun, counterintuitive facts about geometry in high dimensions. For example, take the unit hypercube and inscribe a sphere touching all the sides. How far is a corner of the hypercube from the sphere? (Answer: It diverges to $\infty$ as the dimension grows. The radius of the sphere is $0.5$, but the distance from center to corner of the cube is $0.5\sqrt{n}$.)  

---

### Answer by username_11 on 2015-05-27. Score: 10

A counter intuitive result from complexity theory is the PCP theorem:

Informally, states that for every $NP$ problem $A$, there is an efficient randomized Turing machine that can verify proof correctness (proof of membership in $A$) using logarithmic number of random bits and reading only constant number of bits from the proof. The constant can be reduced to 3 bits. Therefore, the randomized verifier needs to read only three bits from the proclaimed proof.

> **Comments:**
> **username_3**: What is the reference for "can be reduced to 3 bits"?  
> **username_12**: That is known as Håstad's 3 bit (or 3 query) PCP theorem, and it requires sacrificing perfect completeness  
> **username_11**: Here you find further information and the reference to  Håstad's paper: http://people.csail.mit.edu/madhu/papers/1998/glst.pdf  
> **username_1**: @JoeBebel Actually there are 3-bit verifiers with perfect completeness. Hastad's verifier is "linear": it samples three bits and takes their XOR. For such a verifier you do need to sacrifice perfect completeness. BTW, there are PCP proofs that read only two bits (again necessarily without perfect completeness). For example see my answer here http://cstheory.stackexchange.com/a/20549/4896  

---

### Answer by username_10 on 2015-05-30. Score: 9

One thing that proves to be counterintuitive for CS undergraduates, is the fact that one can select the $i$-th order statistics from an unsorted array of $n$ elements in $O(n)$ time. All of the students think they must first necessarily sort the array (in $O(n~lg ~n)$ time).


---

### Answer by username_13 on 2015-05-26. Score: 7

building on MdBs answer/ angle, a classic result of something counterintuitive *at the time of discovery* in TCS at its foundations is the existence of [(un)decidability](http://en.wikipedia.org/wiki/Undecidable_problem) itself. at the turn of the 20th century Hilbert, mirroring the thinking of other leading mathematicians of the time, thought that mathematics could be *systematized* (somewhat in the form of what we now recognize as *algorithmic*) & somewhat via the concept of ["finitism"](http://en.wikipedia.org/wiki/Finitism) (which has rough parallels to the idea of an algorithm as a finite sequence of steps). he proposed famous open problems along these lines. his (and others) intuition turned out to be wrong in a sort of spectacular way. the counterproof is [Godels theorem](http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems) and [Turings Halting problem](http://en.wikipedia.org/wiki/Halting_problem). both were initially extremely abstract concepts/ results and long, highly technical papers/ arguments only understandable to leading mathematicians of the time, but now are refined to simpler conceptual structures and taught to undergraduates. these were not initially seen as two aspects/face of the same phenomenon but now they are.

also it took close to ~¾ of a century to prove that integer Diophantine equations are undecidable, [Hilberts 10th problem](http://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem). this is counterintuitive in the sense that it was always known that number theory was extremely *difficult* but the concept that some specific/ identifiable problems in it may actually be *"impossible to resolve"* was nearly shocking at the time to some. undecidability continues to be a deep challenge in math/ TCS even as we have decades of exponential increases in hardware due to Moores law and yet massive supercomputers that are in a sense still "powerless against it". some aspects of the surprise of undecidability can be found in the book [Mathematics, Loss of Certainty](http://rads.stackoverflow.com/amzn/click/0195030850) by Klein.

> **Comments:**
> **username_14**: Turing's paper was _not_ extremely abstract/technical. It's actually quite straightforward and accessible.  
> **username_13**: fine, maybe for _you, now,_ but how many _undergraduates_ do you know who can follow the _entire_ paper? did _you_ follow it as an undergraduate? why are the _full actual contents_ not covered in undergrad classes? why has an _[entire book](http://www.amazon.com/The-Annotated-Turing-Historic-Computability/dp/0470229055)_ been written analyzing that single paper? what about parts that anticipate concepts not discovered until _decades later_ such as _curry-howard_ correspondence, high level programming languages, etc?  
> **username_1**: Still, "long, highly technical papers/ arguments only understandable to leading mathematicians of the time" is not accurate wrt Turing's paper, which is orders of magnitude more accessible than Godel's papers. This answer is full of non-sequitirs. I cannot see what finitism has to do with Hilbert's program (I am certain he would not have been a finitist). What Moore's law has to do with undecidability is also a puzzle to me. Would you really expect exponentially faster hardware would solve *undecidable* problems?  
> **username_13**: _lol_ Hilbert was involved in _inventing/ originating_ the concept of finitism. agreed the short answer could be "filled out" further. more details in [chat] for anyone _openminded_ / willing to _listen_  
> **username_14**: _why are the full actual contents not covered in undergrad classes?_ — Not enough time.  
> **username_1**: Fair enough, I did not know about Hilbert's finitism. I was only familiar with modern and much stricter notions of finitism. It would be better if you wrote a good answer rather than refer people to chat, but I somehow doubt you'd follow this advice.  

---

### Answer by username_15 on 2015-10-16. Score: 6

It seems obvious, but from personal experience, the idea that you can estimate the median of a collection of items using a constant number of operations is a little shocking. And if that seems a little too technical, you can always convert it into a statement about polls an elections (you need 1300 people to get a sample with 3% error, regardless of the population size).

Related to this is the [birthday paradox](https://en.wikipedia.org/wiki/Birthday_problem) of course.


---

### Answer by username_16 on 2015-05-26. Score: 5

Perhaps a good example (not directly related to computational complexity) is the Turing universality of simple computational models.

For example the [rule 110](http://en.wikipedia.org/wiki/Rule_110) is efficiently (weakly) universal:

Given an (infinite) array of 0-1 (white-black) cells properly initialized and the simple substitution rules:

![enter image description here](https://i.sstatic.net/3EGbX.png)

we have a "working computer"! :-)

For the definition of "weakly" and "efficient", and for other examples of simple universal Turing machines look at: [Turlough Neary, Damien Woods; The complexity of small universal Turing machines: a survey](http://arxiv.org/abs/1110.2230).

Another puzzling example is the Turing completeness of the [FRACTRAN](http://en.wikipedia.org/wiki/FRACTRAN) "programming language":

* the "program" is a list of fractions: $(p\_1/q\_1, p\_2/q\_2,..., p\_n/q\_n)$;
* given an input $n$ find the first $q\_i$ that divides $n$ and replace $n \leftarrow n \cdot \frac{p\_i}{q\_i}$;
* repeat the previous step until no $q\_i$ divides $n$.

With a suitable encoding of the input $n$, FRACTRAN can simulate any Turing machine.

You can also use other models, like cyclic tag systems, ant-automata, ....  
The not-so-intuitive idea is that "computation" is hidden almost everywhere ... Wolfram wrote 1192 pages filled with figures and text to better express that idea in his [A New Kind of Science](https://www.wolframscience.com/nksonline/toc.html) (yes... yes... despite some critical reviews I finally bought a hard-copy of it :-)


---

### Answer by username_17 on 2015-06-06. Score: 3

A few good candidates off the top of my head:

* Every NFA has an equivalent DFA
* There exists a finite field of size $p$ or $p^i$ where $i \in \mathbb{N}$ and $i > 0$.
* Public key cryptography

  + Calling to a function with encrypted arguments and receiving the desired result without revealing information about your inputs
  + RSA encrpytion
* Reed-Solomon codes
* Countability

  + $|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{N} \times \mathbb{N}| = |\mathbb{Q}|$
  + The set of elements in the language $\{0,1\}^\*$ is countable, but $\mathbb{R}$ is uncountable (Cantor's diagonalization)
  + Cantor's Theorem: $|S| < |\mathcal{P}(S)|$
* On a more philosophical level, it astonished me that Turing machines accurately define computation


---

