<p>I think that - <em>independently from the P vs NP question</em> - the <a href="http://en.wikipedia.org/wiki/Cook%27s_theorem">Cook-Levin theorem</a> (and the related notion of NP-completeness)  is another very good candidate; if you have an (efficient) solver for SAT then you have an (efficient) solver for any problem in NP .... and you can end up with something astonishing at least for me:</p>

<ul>
<li>solving $a x_1^2 + b x_2 + c = 0$ over non-negative integers variables;</li>
<li>solving a Sudoku;</li>
<li>finding an Hamiltonian path in a graph;</li>
<li>solving a subset sum instance;</li>
<li>and many other (real life) problems ...</li>
</ul>

<p>are in some sense "equivalent problems"; so if your boss asks you to create a program for packing boxes into a container ... you can give him a Minesweeper solver ... :-) </p>

CC BY-SA 3.0
2014-02-09T00:43:54.443Z
2014-02-09T00:56:47.370Z
2014-02-09T00:56:47.370Z
Marzio De Biasi
<p>A fun example and entertaining one is the undecidability of the tiling problem of Wang tiles. The result follows directly from the undecidability of the Halting problem by a simple simulation of Turing machines using Wang tiles. Interestingly, the undecidability of tiling problem for Wang tiles led to the beautiful result that there are tile sets that tile the plane only aperiodicaly.</p>

<p>Wang conjectured that every tile set that tile the plane must have periodic tiling. Therefore, the conjecture implied that the tiling problem is decidable. Later, Burger proved the undecidability of the tiling problem which implied the existence of tile sets that tile the plane only aperiodicaly.</p>

<p>The bounded version of the tiling problem is $NP$-complete which can be used as a master problem for $NP$-completeness results.</p>

CC BY-SA 3.0
2014-02-08T20:39:59.790Z
2014-02-08T21:39:17.373Z
2014-02-08T21:39:17.373Z
Mohammad Al-Turkistany
<p>favorites collected from here &amp; elsewhere</p>

<ul>
<li><p><a href="http://en.wikipedia.org/wiki/Public_key_cryptography" rel="nofollow">public key cryptography</a> / <a href="http://en.wikipedia.org/wiki/Rsa_algorithm" rel="nofollow">RSA algorithm</a>, <a href="http://en.wikipedia.org/wiki/Trapdoor_function" rel="nofollow">trapdoor functions</a>, <a href="http://compgeom.cs.uiuc.edu/~jeffe/teaching/497/13-circuits.pdf" rel="nofollow">Shannons counting argument showing most circuit functions are hard</a>; re this mystery:</p>

<blockquote>
  <p>13.2 Most Functions Are Hard, But We Don’t Have Any Bad Examples<br>
  To the everlasting shame of theoretical computer scientists everywhere, there is no known explicit example of a family of [hard] functions...</p>
</blockquote></li>
<li><p><a href="http://en.wikipedia.org/wiki/AKS_primality_test" rel="nofollow">AKS Primality testing in P</a>, relatively recent TCS breakthrough easily communicated</p></li>
<li><p><a href="http://en.wikipedia.org/wiki/P_vs_np" rel="nofollow">P vs NP</a>. one elementary way to relate NP functions is through games eg <a href="http://en.wikipedia.org/wiki/Battleship_%28puzzle%29#Computers_and_Battleship" rel="nofollow">battleship</a> or <a href="http://en.wikipedia.org/wiki/Mathematics_of_Sudoku" rel="nofollow">soduku</a> both with NP complete generalizations. also see eg <a href="http://press.princeton.edu/titles/9937.html" rel="nofollow">Fortnows book</a>. see also <a href="http://arxiv.org/abs/1201.4995" rel="nofollow">video games as NP complete</a></p></li>
<li><p>undecidability of <a href="http://en.wikipedia.org/wiki/Post_correspondence_problem" rel="nofollow">Post correspondence problem</a></p></li>
<li><p><a href="http://en.wikipedia.org/wiki/Tseitin-Transformation" rel="nofollow">Tseitin circuit transformation</a> &amp; <a href="http://en.wikipedia.org/wiki/Boolean_satisfiability_problem" rel="nofollow">SAT</a> (re reductions &amp; NP completeness)</p></li>
<li><p><a href="http://en.wikipedia.org/wiki/Euclidean_algorithm" rel="nofollow">(ancient) Euclidean algorithm &amp; worst case analysis connection to Fibonacci sequence</a></p></li>
<li><p><a href="http://en.wikipedia.org/wiki/Curry_Howard" rel="nofollow">Curry-Howard correspondence between proofs and programs</a>. have not seen an elementary ref on this but at heart the idea is quite simple &amp; communicable</p></li>
<li><p><a href="http://en.wikipedia.org/wiki/Four_color_theorem" rel="nofollow">Four color thm</a> via <a href="http://en.wikipedia.org/wiki/Automated_theorem_proving" rel="nofollow">auto thm proving</a>, a breakthrough for TCS</p></li>
</ul>

CC BY-SA 3.0
2014-02-09T03:47:01.397Z
also another very important algorithm with some deep TCS angles: [Pagerank](http://en.wikipedia.org/wiki/PageRank)
vzn
CC BY-SA 3.0
2014-02-08T21:07:17.400Z
2014-02-08T21:07:17.400Z
vzn
<p>Suppose you're meeting with programmers who have taken some professional programming courses (/ self thought) but didn't study a university level math.</p>

<p>In order to show them the beauty of TCS, I'd like to gather some nice results/open questions coming from TCS which can easily be explained.</p>

<p>A good candidate for this purpose (IMHO) will be showing that the halting problem is not decidable. Another will be showing a lower bound on the running time of comparison based sorting (although that's a bit pushing it from what I expect them to understand).</p>

<p>I can also use the ideas from <a href="https://cstheory.stackexchange.com/questions/5188/explain-p-np-problem-to-10-year-old">Explain P = NP problem to 10 year old</a>, assuming some of them are unfamiliar with it.</p>

<p>So, questions has to be:</p>

<p>(0. Beautiful)</p>

<ol>
<li>Explainable with (at most) high school math.</li>
<li>(preferably) not trivial enough to be shown in professional programming courses (for C++/Java/Web/etc.).</li>
</ol>

CC BY-SA 3.0
2014-02-12T16:56:16.813Z
If you want to be heard, you should show them what interests them, not
what interests you. Their idea of beautiful may differ from yours.
The one thing I love about theory is that it can give perpective, and
it can change the way you look at a problem so that what looked hard
suddendly becomes almost trivial.
babou
CC BY-SA 3.0
2014-02-06T12:40:25.950Z
Isn't this entirely opinion-based?
David Richerby
CC BY-SA 3.0
2014-02-06T12:43:45.180Z
Yes, I'm looking for ideas.
R B
CC BY-SA 3.0
2014-02-06T14:02:08.087Z
I'm not sure this is compatible with our [site policy](http://cstheory.stackexchange.com/help/dont-ask) on subjective questions.
David Richerby
CC BY-SA 3.0
2014-02-06T15:44:23.847Z
I think it's a good question. Similar, fruitful questions on mathoverflow: http://mathoverflow.net/questions/47214/how-to-present-mathematics-to-non-mathematicians/47830 . http://mathoverflow.net/questions/56547/applications-of-mathematics .
usul
CC BY-SA 3.0
2014-02-06T15:45:51.527Z
Program obfuscation comes to mind.
usul
CC BY-SA 3.0
2014-02-06T16:05:50.003Z
also somewhat similar to ["dinner table description of TCS"](http://cstheory.stackexchange.com/questions/1471/dinner-table-description-of-theoretical-computer-science). imho my favorite is the existence of hard functions proven by Shannon but almost no constructive proofs of any particular hard functions after more than 1/2 century....
vzn
CC BY-SA 3.0
2014-02-06T17:34:46.530Z
Those are some nice references @usul !
R B
CC BY-SA 3.0
2014-02-06T17:56:54.660Z
The existence of quines is always fun to mention to programmers.
Denis
CC BY-SA 3.0
2014-02-06T20:32:29.463Z
maybe it should be community wiki ?
Suresh Venkat
CC BY-SA 3.0
2014-02-06T22:14:51.600Z
Would you like to be able to explain the result or also proofs? You expect them to know some programming, but what do they know about algorithms? I am thinking of things like linear time deterministic selection and union find in inverse ackermann time per operation.
Sasho Nikolov
CC BY-SA 3.0
2014-02-09T15:12:30.847Z
May be [quine](http://en.wikipedia.org/wiki/Quine_(computing)) and relatively fixed point theorem.
Saeed
<soft-question><big-list><big-picture><teaching>
Interesting results in TCS which are easily explainable to programmers without technical background
R B
# Interesting results in TCS which are easily explainable to programmers without technical background

(Asked by: username_0 on 2014-02-06)

Suppose you're meeting with programmers who have taken some professional programming courses (/ self thought) but didn't study a university level math.

In order to show them the beauty of TCS, I'd like to gather some nice results/open questions coming from TCS which can easily be explained.

A good candidate for this purpose (IMHO) will be showing that the halting problem is not decidable. Another will be showing a lower bound on the running time of comparison based sorting (although that's a bit pushing it from what I expect them to understand).

I can also use the ideas from [Explain P = NP problem to 10 year old](https://cstheory.stackexchange.com/questions/5188/explain-p-np-problem-to-10-year-old), assuming some of them are unfamiliar with it.

So, questions has to be:

(0. Beautiful)

1. Explainable with (at most) high school math.
2. (preferably) not trivial enough to be shown in professional programming courses (for C++/Java/Web/etc.).

**Tags:** soft-question, big-list, big-picture, teaching
> **Comments:**
> **username_2**: Isn't this entirely opinion-based?  
> **username_0**: Yes, I'm looking for ideas.  
> **username_2**: I'm not sure this is compatible with our [site policy](http://cstheory.stackexchange.com/help/dont-ask) on subjective questions.  
> **username_3**: I think it's a good question. Similar, fruitful questions on mathoverflow: http://mathoverflow.net/questions/47214/how-to-present-mathematics-to-non-mathematicians/47830 . http://mathoverflow.net/questions/56547/applications-of-mathematics .  
> **username_3**: Program obfuscation comes to mind.  
> **username_4**: also somewhat similar to ["dinner table description of TCS"](http://cstheory.stackexchange.com/questions/1471/dinner-table-description-of-theoretical-computer-science). imho my favorite is the existence of hard functions proven by Shannon but almost no constructive proofs of any particular hard functions after more than 1/2 century....  
> **username_0**: Those are some nice references @usul !  
> **username_5**: The existence of quines is always fun to mention to programmers.  
> **username_6**: maybe it should be community wiki ?  
> **username_7**: Would you like to be able to explain the result or also proofs? You expect them to know some programming, but what do they know about algorithms? I am thinking of things like linear time deterministic selection and union find in inverse ackermann time per operation.  
> **username_8**: May be [quine](http://en.wikipedia.org/wiki/Quine_(computing)) and relatively fixed point theorem.  
> **username_1**: If you want to be heard, you should show them what interests them, not what interests you. Their idea of beautiful may differ from yours. The one thing I love about theory is that it can give perpective, and it can change the way you look at a problem so that what looked hard suddendly becomes almost trivial.  

---

## 3 answers

### Answer by username_9 on 2014-02-09. Score: 5

I think that - *independently from the P vs NP question* - the [Cook-Levin theorem](http://en.wikipedia.org/wiki/Cook%27s_theorem) (and the related notion of NP-completeness) is another very good candidate; if you have an (efficient) solver for SAT then you have an (efficient) solver for any problem in NP .... and you can end up with something astonishing at least for me:

* solving $a x\_1^2 + b x\_2 + c = 0$ over non-negative integers variables;
* solving a Sudoku;
* finding an Hamiltonian path in a graph;
* solving a subset sum instance;
* and many other (real life) problems ...

are in some sense "equivalent problems"; so if your boss asks you to create a program for packing boxes into a container ... you can give him a Minesweeper solver ... :-)


---

### Answer by username_10 on 2014-02-08. Score: 4

A fun example and entertaining one is the undecidability of the tiling problem of Wang tiles. The result follows directly from the undecidability of the Halting problem by a simple simulation of Turing machines using Wang tiles. Interestingly, the undecidability of tiling problem for Wang tiles led to the beautiful result that there are tile sets that tile the plane only aperiodicaly.

Wang conjectured that every tile set that tile the plane must have periodic tiling. Therefore, the conjecture implied that the tiling problem is decidable. Later, Burger proved the undecidability of the tiling problem which implied the existence of tile sets that tile the plane only aperiodicaly.

The bounded version of the tiling problem is $NP$-complete which can be used as a master problem for $NP$-completeness results.


---

### Answer by username_4 on 2014-02-08. Score: 3

favorites collected from here & elsewhere

* [public key cryptography](http://en.wikipedia.org/wiki/Public_key_cryptography) / [RSA algorithm](http://en.wikipedia.org/wiki/Rsa_algorithm), [trapdoor functions](http://en.wikipedia.org/wiki/Trapdoor_function), [Shannons counting argument showing most circuit functions are hard](http://compgeom.cs.uiuc.edu/~jeffe/teaching/497/13-circuits.pdf); re this mystery:

  > 13.2 Most Functions Are Hard, But We Don’t Have Any Bad Examples  
  > To the everlasting shame of theoretical computer scientists everywhere, there is no known explicit example of a family of [hard] functions...
* [AKS Primality testing in P](http://en.wikipedia.org/wiki/AKS_primality_test), relatively recent TCS breakthrough easily communicated
* [P vs NP](http://en.wikipedia.org/wiki/P_vs_np). one elementary way to relate NP functions is through games eg [battleship](http://en.wikipedia.org/wiki/Battleship_%28puzzle%29#Computers_and_Battleship) or [soduku](http://en.wikipedia.org/wiki/Mathematics_of_Sudoku) both with NP complete generalizations. also see eg [Fortnows book](http://press.princeton.edu/titles/9937.html). see also [video games as NP complete](http://arxiv.org/abs/1201.4995)
* undecidability of [Post correspondence problem](http://en.wikipedia.org/wiki/Post_correspondence_problem)
* [Tseitin circuit transformation](http://en.wikipedia.org/wiki/Tseitin-Transformation) & [SAT](http://en.wikipedia.org/wiki/Boolean_satisfiability_problem) (re reductions & NP completeness)
* [(ancient) Euclidean algorithm & worst case analysis connection to Fibonacci sequence](http://en.wikipedia.org/wiki/Euclidean_algorithm)
* [Curry-Howard correspondence between proofs and programs](http://en.wikipedia.org/wiki/Curry_Howard). have not seen an elementary ref on this but at heart the idea is quite simple & communicable
* [Four color thm](http://en.wikipedia.org/wiki/Four_color_theorem) via [auto thm proving](http://en.wikipedia.org/wiki/Automated_theorem_proving), a breakthrough for TCS

> **Comments:**
> **username_4**: also another very important algorithm with some deep TCS angles: [Pagerank](http://en.wikipedia.org/wiki/PageRank)  

---

