Counterintuitive results for undergraduates

Question

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?

Answer 1

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.
4. The Banach-Tarski "paradox".

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$

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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 6

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 20^th 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.

Answer 7

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.

Answer 8

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

Answer 9

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