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?

• closely related: cstheory.stackexchange.com/q/276/4896 and cstheory.stackexchange.com/q/2802/4896 – Sasho Nikolov May 26 '15 at 3:40
• – user6973 May 26 '15 at 4:02
• The second of Sasho's links is a duplicate, no? – Huck Bennett May 26 '15 at 5:00
• 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 May 26 '15 at 8:11
• For sufficiently large input sizes, primality can always be decided in less time than $\hspace{.85 in}$ the fastest known way to have a non-negligible chance of factoring an RSA modulus. $\hspace{.76 in}$ – user6973 May 26 '15 at 8:24

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.
2. A curve may fill an entire square.
3. There are constant width curves 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.

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.
3. There is a function $f : \mathbb{R} \to \mathbb{R}$ which is discontinuous at all rational numbers and differentiable at all irrational numbers.

For programmers you can try:

1. The impossible functionals: 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 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$ with the following properties:

• the tree $T$ is infinite
• there is no program that traces an infinite path in $T$
• 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. Jun 3 '15 at 0:34
• 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 Jun 3 '15 at 12:10

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 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.
• Besides Misra-Gries, I also think reservoir sampling is simple but nice. – Juho May 26 '15 at 19:16
• @Juho I agree. A popular interview question to boot :). – Sasho Nikolov May 26 '15 at 20:42

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$.

• 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 Jun 7 '15 at 10:38
• 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 Oct 16 '15 at 17:03

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.

• What is the reference for "can be reduced to 3 bits"? – Ryan May 28 '15 at 1:37
• That is known as Håstad's 3 bit (or 3 query) PCP theorem, and it requires sacrificing perfect completeness – Joe Bebel May 28 '15 at 8:30
• Here you find further information and the reference to Håstad's paper: people.csail.mit.edu/madhu/papers/1998/glst.pdf – Mohammad Al-Turkistany May 28 '15 at 9:20
• @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 cstheory.stackexchange.com/a/20549/4896 – Sasho Nikolov May 28 '15 at 18:18

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).

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 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" (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 and Turings 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. 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 by Klein.

• Turing's paper was not extremely abstract/technical. It's actually quite straightforward and accessible. – Jeffε May 30 '15 at 15:03
• 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 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 May 30 '15 at 18:49
• 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 May 30 '15 at 19:15
• why are the full actual contents not covered in undergrad classes? — Not enough time. – Jeffε May 30 '15 at 19:40
• 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 May 31 '15 at 4:40

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 of course.

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

For example the rule 110 is efficiently (weakly) universal:

Given an (infinite) array of 0-1 (white-black) cells properly initialized and the simple substitution rules: 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.

Another puzzling example is the Turing completeness of the 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 (yes... yes... despite some critical reviews I finally bought a hard-copy of it :-)

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