13
$\begingroup$

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, 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.).
| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Isn't this entirely opinion-based? $\endgroup$ – David Richerby Feb 6 '14 at 12:40
  • 6
    $\begingroup$ I think it's a good question. Similar, fruitful questions on mathoverflow: mathoverflow.net/questions/47214/… . mathoverflow.net/questions/56547/applications-of-mathematics . $\endgroup$ – usul Feb 6 '14 at 15:44
  • 1
    $\begingroup$ also somewhat similar to "dinner table description of TCS". 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.... $\endgroup$ – vzn Feb 6 '14 at 16:05
  • 1
    $\begingroup$ The existence of quines is always fun to mention to programmers. $\endgroup$ – Denis Feb 6 '14 at 17:56
  • 2
    $\begingroup$ maybe it should be community wiki ? $\endgroup$ – Suresh Venkat Feb 6 '14 at 20:32
9
$\begingroup$

In addition to the halting problem, I suggest discussing:

Rice's Theorem. Some of the explanation on Wikipedia is a bit jargon-heavy, but it's generally not a hard theorem or proof to understand other than that; it has a lot of relevance to real-world concepts like anti-virus software. The proof is about as involved as the proof of the halting problem (and actually depends on the undecidability of the halting problem). Basically, just understand that a "computable function" is a Turing machine or computer program.

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ I do not think hardness of factoring is known to imply RSA security. $\endgroup$ – Sasho Nikolov Feb 8 '14 at 15:04
  • 1
    $\begingroup$ That was a significant gap in my knowledge of crypto. Thanks for pointing that out; I edited my answer. $\endgroup$ – Philip White Feb 8 '14 at 17:16
  • 1
    $\begingroup$ If you are interested, you may look at this: crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf. However, your example was a nice one, even if the details were incorrect. For Diffie-Hellman, equivalence to discrete log is known for many cyclic group, arguably including the ones used in practical applications: citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.78.3339. Also, Diffie-Hellman is actually easier to explain than RSA, IMO $\endgroup$ – Sasho Nikolov Feb 8 '14 at 18:18
5
$\begingroup$

I think that - independently from the P vs NP question - the Cook-Levin 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 ... :-)

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

favorites collected from here & elsewhere

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ also another very important algorithm with some deep TCS angles: Pagerank $\endgroup$ – vzn Feb 9 '14 at 3:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.