<p>The undecidability of the halting problem. </p>

<p>Beautiful for many reasons. It is an impossibility result. The proof uses diagonalisation. The statement applies to a broad range of models of computation. It can be formulated in a variety of ways, particularly, using standard programming languages. It was a watershed result in the history of computing. Extending this statement leads to Rice's Theorem, Turing degrees and many other cool results. Etc. Etc. Etc.</p>

CC BY-SA 3.0
2012-02-27T10:09:53.990Z
2012-02-27T10:09:53.990Z
Vijay D
<p>The possibility of public-key cryptography, for example, Diffie-Hellman key exchange scheme.</p>

<p>It breaks the very strong preconception that people have to meet before exchanging secrets on an insecure channel.</p>

CC BY-SA 3.0
2012-02-27T15:12:07.480Z
2012-02-27T15:12:07.480Z
aelguindy
<p>I was and still am surprised by Euclid's algorithm. To me, it is a testament to power of human thinking - that <em>people</em> could conceive of such an algorithm so early (around 300 BC if I trust my memory).</p>

<p>Fast forwarding, there is mind numbing literature on the subject. I think <a href="http://www.scottaaronson.com/blog/?p=524">Scott Aaronson's list</a> should be helpful in this regard - though, as Aaronson himself says its not complete (and not entirely theoretical)</p>

CC BY-SA 3.0
2012-02-27T18:44:53.167Z
2012-02-27T18:44:53.167Z
Akash Kumar
<p>In my opinion, the <a href="http://en.wikipedia.org/wiki/Curry_Howard">Curry-Howard correspondence</a> is one of the most beautiful theoretical results, and the one that drove me to do research. </p>

<p>The idea that two systems, programs on the one hand, and proofs on the other hand, have exactly the same structure, is almost of philosophical nature: are there some general "reasoning patterns"? </p>

CC BY-SA 3.0
2012-08-08T14:10:19.390Z
"If only there were some way to automate the process." - I'd go out of a limb and say that this is undecidable.
luis.espinal
CC BY-SA 3.0
2012-02-26T19:11:03.693Z
Personnaly, I consider the Curry-Howard correspondance as the canonical example of duplicated theories due to different contexts whereas they have the same mathematical denotation. It should be rather considered as as shame of humans who aren't able to recognize existing structures and reinvent the wheel.
Ludovic Patey
CC BY-SA 3.0
2012-02-27T10:00:27.887Z
I completely disagree. If Curry-Howard is about puny humans duplicating work, so is much of modern mathematics, particularly results relating structures in combinatorics, algebra and topology.
Vijay D
CC BY-SA 3.0
2012-02-28T18:46:14.657Z
You are right in the sense that mathematics consists mainly of finding correlations between structures, and a correlation is by definition a non-independence, revealing some duplications in at least some parts of the theories. In order to be consistent, I must conclude that mathematics are a shame in its essence because if we were able to see duplications, theorems would be obvious and mathematics useless. ^^
Ludovic Patey
CC BY-SA 3.0
2012-03-02T01:05:57.897Z
Turingoid: I agree. I have come to similar conclusions (about reinventing the wheel) when working with symmetry concept. It is really a shame, that we are unable to work at level of primary symmetry/asymmetry relations. IMO there will be a collapse of some of actual sciences into wider ones when we finally break through.
Mooncer
CC BY-SA 3.0
2012-03-03T03:59:40.447Z
If only there were some way to automate the process.
Jeffε
CC BY-SA 3.0
2012-02-26T14:04:17.943Z
2012-02-26T14:04:17.943Z
Charles
<p>surprisingly one of the most obvious answers not added yet. sometimes one works too much with something to see it impartially. the <a href="http://en.wikipedia.org/wiki/Cook_theorem">theory of NP completeness launched by Cook/Levin</a> and immediately amplified by Karp who gave an early indication of its ubiquitousness, even more prescient in retrospect. in many ways this is the birth of modern TCS &amp; complexity theory, and its core/key/notorious question P=?NP is still open after four decades of intense study/attack. P=?NP has a $1M Claymath award for its solution. </p>

<p>the Cook proof introduced the NDTM which is apparently not at all a mere theoretical curiosity but an almost extremely fundamental part of TCS. launched a thousand ships, so to speak. moreover, it continually resists/defies efforts via one of the other key/powerful TCS techniques mentioned in this list, diagonalization, seen in eg the BGS-75 Oracle/Relativization results-- suggesting that there must be something exotic and different about any possible solution, also further suggested/expanded by the Razborov-Rudich Natural Proofs paper (2007 Godel prize).</p>

<p>there are many, many refs on the subj but one more recent with some 1sthand account of the history can be found in <a href="http://rads.stackoverflow.com/amzn/click/1441971548">The P=?NP Question and Godel's Lost Letter</a> by RJ Lipton</p>

CC BY-SA 3.0
2012-02-28T19:17:24.027Z
Actually, NDTM's already appear in Turing's 1936 paper as "choice machines"; see Wikipedia.
Jeffε
CC BY-SA 3.0
2012-02-29T15:39:16.370Z
oops, ok. thx for correction. anyway the cook paper is maybe 1st to show the NDTM is much different than a DTM in a complexity theory sense.
vzn
CC BY-SA 3.0
2012-02-29T19:26:17.397Z
Oops!  Was just about to post this.  I was also surprised it wasn't posted immediately.
Andrew D. King
CC BY-SA 3.0
2012-02-28T16:27:51.613Z
2012-02-28T16:27:51.613Z
vzn
<p>Yao's technique to use von Neumann's Minmax Theorem to prove lower bounds for Randomized Algorithms. I find it as something out of this world.</p>

<p>Probabilistic method to prove the existence of objects that we find it difficult to construct including the Lovasz Local Lemma. These techniques are so simple, yet so powerful.</p>

<p>Madhu Sudan's coding theory constructions using polynomials.</p>

<p>Expanders (this started off as Ramanujan graphs) and Extractors and their applications in Pseudorandomness.</p>

<p>Cooley and Tukey's Fast Fourier Transform algorithm to find DFT. (Though, as assumed by Tukey, this was a rediscovery of a well known technique, at least known to Gauss!)</p>

<p>Barrington's Theorem, (a very surprising result in its time)</p>

<p>Parallel  Repetition Theorem (though the result is nice, the proof is not easy)</p>

<p>Lovasz Theta function to estimate the shannon capacity of a graph.</p>

<p>Ellipsoid algorithm that showed that LP is in P, surprising many at a time when many still suspected it could be NP-Complete.</p>

CC BY-SA 3.0
2014-05-19T16:19:30.827Z
The probabilistic method is not really a result. It's just an immediate feature of the definition of probability. For similar reasons it's hard to argue it is special to TCS (despite there being a book with the same name).
Simd
CC BY-SA 3.0
2012-02-29T17:04:15.500Z
2012-03-19T09:38:02.720Z
2012-03-19T09:38:02.720Z
karthik
<p><a href="http://en.wikipedia.org/wiki/Kolmogorov_complexity">Kolmogorov Complexity</a> and the <em>incompressibility method</em>.</p>

<p>The incompressibility method - based on Kolmogorov complexity - provided a new and intuitive way of formulating proofs.  In a typical proof using incompressibility method, one first chooses an incompressible object from the class under discussion. The argument invariably says that if a desired property does not hold, then, in contrast with the assumption, the object can be compressed and this yelds the required contradiction.</p>

<p>See for example the proof that there is an infinite number of primes, the alternative proof of the Godel's incompleteness theorem, or the <a href="http://people.cs.uchicago.edu/~fortnow/papers/quaderni.pdf">connections between Kolmogorov Complexity and Computational Complexity</a>, ....</p>

CC BY-SA 3.0
2012-02-28T14:48:09.147Z
2012-02-29T17:14:49.737Z
2012-02-29T17:14:49.737Z
Marzio De Biasi
<p>A beautiful result which builds on the PCP theorem states that it is computationally hard (NP-hard) to satisfy more than 7/8 of the clauses of 3SAT formula even for satisfiable ones.</p>

CC BY-SA 3.0
2012-02-28T08:17:59.787Z
Even more amazing since 7/8 of the clauses can be satisfied quite trivially (by a random assignment or a greedy algorithm.)
Jan Johannsen
CC BY-SA 3.0
2012-02-28T15:42:23.980Z
This result isn't exactly the PCP theorem. It builds on the PCP theorem but needs much more work than that.
Mahdi Cheraghchi
CC BY-SA 3.0
2012-02-27T19:36:44.660Z
2012-02-29T13:40:42.660Z
2012-02-29T13:40:42.660Z
Mohammad Al-Turkistany
<p>Shannon's source and channel coding theorems. </p>

<p>A mathematical definition that distinguished between the transmitted, receiver and medium and which ignored the semantics of the message was a big step. Entropy, in the context of data is a fantastically useful notion.  And because information theory should be better known.</p>

CC BY-SA 3.0
2013-06-20T20:05:32.180Z
Also note that Shannon almost invented information theory in its seminal paper.
Alejandro Piad
CC BY-SA 3.0
2012-02-28T07:13:10.953Z
2012-02-28T07:13:10.953Z
Vijay D
<p><a href="http://en.wikipedia.org/wiki/Shors_algorithm">shors algorithm for factoring in BQP</a>. in my opinion/memory, quantum computation was more just a theoretical curiosity until this result in 1994, at which point it seems the literature and research interest into QM computing exploded. its still arguably one of the most important QM algorithms known. awarded the 1999 Gödel prize. it also reveals that factoring in QM computation is actually in a sense somewhat better understood than in classical computing where eg the question of whether Factoring is NP complete is still open.</p>

CC BY-SA 3.0
2012-02-28T16:32:41.060Z
note that factoring being NP-complete would be a big shock, as it would imply coNP = NP
Sasho Nikolov
CC BY-SA 3.0
2012-02-29T13:29:12.253Z
I would put Simon's algorithm together with Shor's.
Juan Bermejo Vega
CC BY-SA 3.0
2012-02-27T19:45:46.070Z
2012-02-27T19:45:46.070Z
vzn
<p>I was (and still am) astonished by <a href="http://en.wikipedia.org/wiki/Kleene%27s_recursion_theorem">Kleene's Second Recursion Theorem</a>. On the surface, it seems simple and not very useful but I later found out it's deep both mathematically and philosophically.</p>

<p>When I also read about the variant proven on Turing Machines (very very informally stating that machines can obtain their own descriptions or equivalently that there are machines that output their own description, like a program that prints itself..), I felt my brain twist so hard, yet intrigued like never before. Then, you see how the theorem is used to give one line proofs for undecidability of halting problem and unrecognizability of minimal machines..etc.</p>

CC BY-SA 3.0
2012-02-26T17:53:50.193Z
2012-02-26T17:53:50.193Z
aelguindy
<p>I think <a href="http://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem" rel="nofollow">graph minor theorem</a> by Robertson and Seymour was most wonderful theories I ever seen (and partially read it). First of all it's quiet complicated, but base conjectures are not hard and may be everyone working in TCS can guess them. Their extreme effort to prove them was wonderful. In fact after I read some of the papers in that series I understand power of human mind.</p>

<p>Also graph minor theorem has a great impact on different fields of TCS. Like graph theory, approximation algorithm, parametrized algorithms, logic, ...</p>

CC BY-SA 3.0
2012-02-29T11:00:46.710Z
2014-05-13T21:14:40.753Z
2014-05-13T21:14:40.753Z
Saeed
<p>seems to me the <a href="http://en.wikipedia.org/wiki/AKS_primality_test">AKS P-time primality test</a> is quite beautiful in various senses. a breakthrough at the time, one of the great but rather rare breakthroughs seen in complexity theory in our lifetimes. it solves a problem dating back to greek antiquity &amp; relates to some of the earliest algorithms invented (sieve of eratosthenes), ie identifying primes efficiently. its a constructive proof that primality detection is in P as opposed to many great proofs that are unfortunately nonconstructive. </p>

<p>its interconnected to the RSA cryptography algorithm mentioned in another answer because that algorithm needs to find large primes quickly, prior to the AKS algorithm this was only probabilistically possible. its fundamentally connected to number theory &amp; other deep problems eg the Riemann conjecture which in many ways is the original realm of algorithmics.</p>

<p>awarded the 2006 Gödel Prize and the 2006 Fulkerson Prize</p>

CC BY-SA 3.0
2012-03-07T19:32:54.900Z
dont know why people would consider the probabilistic algorithm superior in beauty to the exact algorithm. yes, AKS is largely based on [Miller-Rabin](http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test) but is major advance removing the randomization that was missed (or maybe not seen as possible) for decades & finally found. to me thats beautiful. moreover number theory is just a beautiful area of mathematics/algorithmics [with the theory of primes starring in number theory], this perspective can be seen in eg the famous book Mathematicians Apology by GH Hardy.
vzn
CC BY-SA 3.0
2012-02-28T19:14:56.463Z
This is definitely an important result, but beautiful?  Really?
Jeffε
CC BY-SA 3.0
2012-02-29T06:20:29.567Z
I agree with the above comment by JeffE. The result is vastly significant and thats what has been pointed out in the answer, rather than how (or what idea(s) used in) AKS primality testing is/are beautiful.
Nikhil
CC BY-SA 3.0
2012-02-29T15:36:16.173Z
to me a "vastly significant" result is beautiful. "your mileage may vary".
vzn
CC BY-SA 3.0
2012-02-29T21:08:55.973Z
Miller-Rabin is quite beautiful, on the other hand
Sasho Nikolov
CC BY-SA 3.0
2012-02-27T19:34:34.277Z
2012-02-27T19:47:38.757Z
2012-02-27T19:47:38.757Z
vzn
<p>There are lots of lovely results about probabilistic algorithms, which are deceptively simple and a great step forward in the way we think about computation.</p>

<p>von Neumann's trick for implementing a fair coin with a  biased one. We are so used to probabilistic algorithms now, but from an outside perspective, this is unbelieveably cool. Both the algorithm and proof are accessible to anyone who knows high-school probability.  </p>

CC BY-SA 3.0
2012-02-28T17:43:25.037Z
I would have expected you to mention Yao's minmax principle for finding lower bounds on the expected running times of Las Vegas algorithms. It connects ideas of game theory with probability and algorithms.
karthik
CC BY-SA 3.0
2012-02-28T18:36:09.630Z
Sure. But I'm spamming this question with enough answers already. Please add your favourite result as an answer.
Vijay D
CC BY-SA 3.0
2012-02-27T19:56:39.523Z
2012-02-27T19:56:39.523Z
Vijay D
<p>One of my favourite family of results is that various problems of a seemingly infinite nature are decidable. </p>

<ol>
<li>The first order theory of real closed fields is decidable (by Tarski). Euclidean geometry is also a model of the axioms of real-closed fields, hence, by Tarski, first order statements in this model are decidable.</li>
<li>Presburger arithmetic is decidable. </li>
<li>First order theory of algebraically closed fields (this includes complex numbers) is decidable. </li>
<li>Monadic second order logic over infinite (and finite) words is decidable. The proof is elegant and can be taught to undergrads. </li>
</ol>

CC BY-SA 3.0
2012-02-27T10:26:41.637Z
2012-02-27T10:26:41.637Z
Vijay D
<p>The result by Tim Griffin that control operators such as <code>call/cc</code> are related to classical logic, extending the Curry-Howard correspondence.  </p>

<p>Basically, the typing of <code>call/cc</code> is such that if $E$ has type $\neg\neg \tau$, then $\mathtt{call/cc}{(E)}$ has type $\tau$.  This works out when interpreting the type $\neg\tau$ as $\tau\rightarrow\bot$, as is standard in logic, and corresponds to the type of a function that takes a $\tau$ and never returns.  That's exactly what a continuation does, making the correspondence work.</p>

<p>His <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.6893">paper</a>, "A Formulae-as-types notion of control", appears in POPL 1990.</p>

CC BY-SA 3.0
2012-02-28T18:18:27.080Z
2012-02-29T01:35:03.107Z
2012-02-29T01:35:03.107Z
Sam Tobin-Hochstadt
<p>My favorite is Rabin's linear time algorithm for computing the closest pair of points in the plane (or more precisely its simplification). It get across the importance of the computation model, the power of randomized algorithms, and some elegant way to think about randomized algorithms.</p>

<p>This said, CS is still far from achieving the level of elegance one encounters in mathematics (well, they had 5000 years head start), from basic definitions/results in calculus, topology (fixed point theorems), combinatorics, geometry (Pythagorean theorem <a href="http://en.wikipedia.org/wiki/File:Pythag_anim.gif">http://en.wikipedia.org/wiki/File:Pythag_anim.gif</a>), etc. </p>

<p>If you look for beauty, look for it everywhere...</p>

CC BY-SA 3.0
2012-02-29T03:08:08.613Z
2012-02-29T03:08:08.613Z
Sariel Har-Peled
<p>This result is probably a bit recent to qualify as fundamental, but I believe that the <em>types-as-homotopy-types</em> interpretation qualifies. This view allows interpreting types from <a href="http://en.wikipedia.org/wiki/Intuitionistic_type_theory">constructive type theory</a> as sets with certain geometric properties, in this case <a href="http://en.wikipedia.org/wiki/Homotopy">homotopy</a>.</p>

<p>I find this point of view to be particularly beautiful as it makes certain previously complex observations about type theory simple, for instance the fact that<a href="http://homotopytypetheory.org/2011/04/10/just-kidding-understanding-identity-elimination-in-homotopy-type-theory/">"axiom K" is not derivable</a>.</p>

<p>An overview of this budding field by Steve Awodey can be found <a href="http://www.andrew.cmu.edu/user/awodey/preprints/TTH.pdf">here</a>.</p>

CC BY-SA 3.0
2012-02-27T14:05:36.673Z
2012-02-27T14:05:36.673Z
cody
<p><a href="http://en.wikipedia.org/wiki/Zero-knowledge_proof" rel="nofollow">Zero-knowledge proof</a> is a very interesting concept. It allows for an entity, the prover, to prove (with high probability) to another entity, the verifier, that it knows "a secret" (a solution to some NP-problem, a modular square-root of some number, a discrete log of some number etc …) without giving any information at all about the secret (which is difficult at first glance, since the first idea for proving that you know a secret is to actually tell the secret, and that any communication that could result in the verifier believing that you know the secret can a priori only increase the knowledge of the verifier about the secret).</p>

CC BY-SA 3.0
2014-05-14T17:48:23.167Z
2014-05-14T17:48:23.167Z
Hugo Vincennes
<p>Recently, a friend of mine (working in TCS) mentioned in a conversation that "he wanted to see/know all (or as much as possible) of the beautiful results in TCS in his lifetime". This kind of made me wonder about the beautiful results in this area and hence the motivation for the following question:</p>

<p>Which results (or ideas), in your opinion, are beautiful in theoretical computer science? It would be great if you mentioned the reason as well. 
[Would also be fine even if the ideas originate in mathematics, but have aroused interest and found uses in TCS]</p>

<p>I would start with an answer as Cantor's diagonal argument because it's simple, elegant and yet a powerful result. </p>

CC BY-SA 3.0
2012-02-26T15:40:35.667Z
Near-duplicate of [this question](http://cstheory.stackexchange.com/questions/189/algorithms-from-the-book) (but only near, because algorithms is a proper subset of TCS)
Jeffε
CC BY-SA 3.0
2012-02-26T19:28:10.397Z
I am not if this is a good question in its current form, please see [Good Subjective, Bad Subjective](http://blog.stackoverflow.com/2010/09/good-subjective-bad-subjective/).
Kaveh
CC BY-SA 3.0
2012-02-27T03:41:49.913Z
At the very least, this needs to be CW.
Suresh Venkat
CC BY-SA 3.0
2012-02-27T19:57:39.303Z
Maybe we could modify the question to focus on non-algorithmic results -- seeing as the other thread is about algorithms.
Vijay D
CC BY-SA 3.0
2012-02-28T16:46:13.993Z
In his blog, Lance Fortnow has lists of "favorite theorems" of each decade. There are quite a bit of beautiful results in those lists.
Mahdi Cheraghchi
<soft-question><big-list>
Beautiful results in TCS
Nikhil
# Beautiful results in TCS

(Asked by: username_0 on 2012-02-26)

Recently, a friend of mine (working in TCS) mentioned in a conversation that "he wanted to see/know all (or as much as possible) of the beautiful results in TCS in his lifetime". This kind of made me wonder about the beautiful results in this area and hence the motivation for the following question:

Which results (or ideas), in your opinion, are beautiful in theoretical computer science? It would be great if you mentioned the reason as well.
[Would also be fine even if the ideas originate in mathematics, but have aroused interest and found uses in TCS]

I would start with an answer as Cantor's diagonal argument because it's simple, elegant and yet a powerful result.

**Tags:** soft-question, big-list

> **Comments:**
> **username_1**: Near-duplicate of [this question](http://cstheory.stackexchange.com/questions/189/algorithms-from-the-book) (but only near, because algorithms is a proper subset of TCS)  
> **username_2**: I am not if this is a good question in its current form, please see [Good Subjective, Bad Subjective](http://blog.stackoverflow.com/2010/09/good-subjective-bad-subjective/).  
> **username_3**: At the very least, this needs to be CW.  
> **username_4**: Maybe we could modify the question to focus on non-algorithmic results -- seeing as the other thread is about algorithms.  
> **username_5**: In his blog, Lance Fortnow has lists of "favorite theorems" of each decade. There are quite a bit of beautiful results in those lists.  

---

## 19 answers

### Answer by username_4 on 2012-02-27. Score: 23

The undecidability of the halting problem.

Beautiful for many reasons. It is an impossibility result. The proof uses diagonalisation. The statement applies to a broad range of models of computation. It can be formulated in a variety of ways, particularly, using standard programming languages. It was a watershed result in the history of computing. Extending this statement leads to Rice's Theorem, Turing degrees and many other cool results. Etc. Etc. Etc.


---

### Answer by username_6 on 2012-02-27. Score: 19

The possibility of public-key cryptography, for example, Diffie-Hellman key exchange scheme.

It breaks the very strong preconception that people have to meet before exchanging secrets on an insecure channel.


---

### Answer by username_7 on 2012-02-27. Score: 17

I was and still am surprised by Euclid's algorithm. To me, it is a testament to power of human thinking - that *people* could conceive of such an algorithm so early (around 300 BC if I trust my memory).

Fast forwarding, there is mind numbing literature on the subject. I think [Scott Aaronson's list](http://www.scottaaronson.com/blog/?p=524) should be helpful in this regard - though, as Aaronson himself says its not complete (and not entirely theoretical)


---

### Answer by username_8 on 2012-02-26. Score: 17

In my opinion, the [Curry-Howard correspondence](http://en.wikipedia.org/wiki/Curry_Howard) is one of the most beautiful theoretical results, and the one that drove me to do research.

The idea that two systems, programs on the one hand, and proofs on the other hand, have exactly the same structure, is almost of philosophical nature: are there some general "reasoning patterns"?

> **Comments:**
> **username_10**: Personnaly, I consider the Curry-Howard correspondance as the canonical example of duplicated theories due to different contexts whereas they have the same mathematical denotation. It should be rather considered as as shame of humans who aren't able to recognize existing structures and reinvent the wheel.  
> **username_4**: I completely disagree. If Curry-Howard is about puny humans duplicating work, so is much of modern mathematics, particularly results relating structures in combinatorics, algebra and topology.  
> **username_10**: You are right in the sense that mathematics consists mainly of finding correlations between structures, and a correlation is by definition a non-independence, revealing some duplications in at least some parts of the theories. In order to be consistent, I must conclude that mathematics are a shame in its essence because if we were able to see duplications, theorems would be obvious and mathematics useless. ^^  
> **username_11**: Turingoid: I agree. I have come to similar conclusions (about reinventing the wheel) when working with symmetry concept. It is really a shame, that we are unable to work at level of primary symmetry/asymmetry relations. IMO there will be a collapse of some of actual sciences into wider ones when we finally break through.  
> **username_1**: If only there were some way to automate the process.  
> **username_9**: "If only there were some way to automate the process." - I'd go out of a limb and say that this is undecidable.  

---

### Answer by username_12 on 2012-02-28. Score: 16

surprisingly one of the most obvious answers not added yet. sometimes one works too much with something to see it impartially. the [theory of NP completeness launched by Cook/Levin](http://en.wikipedia.org/wiki/Cook_theorem) and immediately amplified by Karp who gave an early indication of its ubiquitousness, even more prescient in retrospect. in many ways this is the birth of modern TCS & complexity theory, and its core/key/notorious question P=?NP is still open after four decades of intense study/attack. P=?NP has a $1M Claymath award for its solution.

the Cook proof introduced the NDTM which is apparently not at all a mere theoretical curiosity but an almost extremely fundamental part of TCS. launched a thousand ships, so to speak. moreover, it continually resists/defies efforts via one of the other key/powerful TCS techniques mentioned in this list, diagonalization, seen in eg the BGS-75 Oracle/Relativization results-- suggesting that there must be something exotic and different about any possible solution, also further suggested/expanded by the Razborov-Rudich Natural Proofs paper (2007 Godel prize).

there are many, many refs on the subj but one more recent with some 1sthand account of the history can be found in [The P=?NP Question and Godel's Lost Letter](http://rads.stackoverflow.com/amzn/click/1441971548) by RJ Lipton

> **Comments:**
> **username_1**: Actually, NDTM's already appear in Turing's 1936 paper as "choice machines"; see Wikipedia.  
> **username_12**: oops, ok. thx for correction. anyway the cook paper is maybe 1st to show the NDTM is much different than a DTM in a complexity theory sense.  
> **username_13**: Oops!  Was just about to post this.  I was also surprised it wasn't posted immediately.  

---

### Answer by username_14 on 2012-02-29. Score: 16

Yao's technique to use von Neumann's Minmax Theorem to prove lower bounds for Randomized Algorithms. I find it as something out of this world.

Probabilistic method to prove the existence of objects that we find it difficult to construct including the Lovasz Local Lemma. These techniques are so simple, yet so powerful.

Madhu Sudan's coding theory constructions using polynomials.

Expanders (this started off as Ramanujan graphs) and Extractors and their applications in Pseudorandomness.

Cooley and Tukey's Fast Fourier Transform algorithm to find DFT. (Though, as assumed by Tukey, this was a rediscovery of a well known technique, at least known to Gauss!)

Barrington's Theorem, (a very surprising result in its time)

Parallel Repetition Theorem (though the result is nice, the proof is not easy)

Lovasz Theta function to estimate the shannon capacity of a graph.

Ellipsoid algorithm that showed that LP is in P, surprising many at a time when many still suspected it could be NP-Complete.

> **Comments:**
> **username_15**: The probabilistic method is not really a result. It's just an immediate feature of the definition of probability. For similar reasons it's hard to argue it is special to TCS (despite there being a book with the same name).  

---

### Answer by username_16 on 2012-02-28. Score: 14

[Kolmogorov Complexity](http://en.wikipedia.org/wiki/Kolmogorov_complexity) and the *incompressibility method*.

The incompressibility method - based on Kolmogorov complexity - provided a new and intuitive way of formulating proofs. In a typical proof using incompressibility method, one first chooses an incompressible object from the class under discussion. The argument invariably says that if a desired property does not hold, then, in contrast with the assumption, the object can be compressed and this yelds the required contradiction.

See for example the proof that there is an infinite number of primes, the alternative proof of the Godel's incompleteness theorem, or the [connections between Kolmogorov Complexity and Computational Complexity](http://people.cs.uchicago.edu/~fortnow/papers/quaderni.pdf), ....


---

### Answer by username_17 on 2012-02-27. Score: 13

A beautiful result which builds on the PCP theorem states that it is computationally hard (NP-hard) to satisfy more than 7/8 of the clauses of 3SAT formula even for satisfiable ones.

> **Comments:**
> **username_18**: Even more amazing since 7/8 of the clauses can be satisfied quite trivially (by a random assignment or a greedy algorithm.)  
> **username_5**: This result isn't exactly the PCP theorem. It builds on the PCP theorem but needs much more work than that.  

---

### Answer by username_4 on 2012-02-28. Score: 11

Shannon's source and channel coding theorems.

A mathematical definition that distinguished between the transmitted, receiver and medium and which ignored the semantics of the message was a big step. Entropy, in the context of data is a fantastically useful notion. And because information theory should be better known.

> **Comments:**
> **username_19**: Also note that Shannon almost invented information theory in its seminal paper.  

---

### Answer by username_12 on 2012-02-27. Score: 11

[shors algorithm for factoring in BQP](http://en.wikipedia.org/wiki/Shors_algorithm). in my opinion/memory, quantum computation was more just a theoretical curiosity until this result in 1994, at which point it seems the literature and research interest into QM computing exploded. its still arguably one of the most important QM algorithms known. awarded the 1999 Gödel prize. it also reveals that factoring in QM computation is actually in a sense somewhat better understood than in classical computing where eg the question of whether Factoring is NP complete is still open.

> **Comments:**
> **username_20**: note that factoring being NP-complete would be a big shock, as it would imply coNP = NP  
> **username_21**: I would put Simon's algorithm together with Shor's.  

---

### Answer by username_6 on 2012-02-26. Score: 11

I was (and still am) astonished by [Kleene's Second Recursion Theorem](http://en.wikipedia.org/wiki/Kleene%27s_recursion_theorem). On the surface, it seems simple and not very useful but I later found out it's deep both mathematically and philosophically.

When I also read about the variant proven on Turing Machines (very very informally stating that machines can obtain their own descriptions or equivalently that there are machines that output their own description, like a program that prints itself..), I felt my brain twist so hard, yet intrigued like never before. Then, you see how the theorem is used to give one line proofs for undecidability of halting problem and unrecognizability of minimal machines..etc.


---

### Answer by username_22 on 2012-02-29. Score: 11

I think [graph minor theorem](http://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem) by Robertson and Seymour was most wonderful theories I ever seen (and partially read it). First of all it's quiet complicated, but base conjectures are not hard and may be everyone working in TCS can guess them. Their extreme effort to prove them was wonderful. In fact after I read some of the papers in that series I understand power of human mind.

Also graph minor theorem has a great impact on different fields of TCS. Like graph theory, approximation algorithm, parametrized algorithms, logic, ...


---

### Answer by username_12 on 2012-02-27. Score: 10

seems to me the [AKS P-time primality test](http://en.wikipedia.org/wiki/AKS_primality_test) is quite beautiful in various senses. a breakthrough at the time, one of the great but rather rare breakthroughs seen in complexity theory in our lifetimes. it solves a problem dating back to greek antiquity & relates to some of the earliest algorithms invented (sieve of eratosthenes), ie identifying primes efficiently. its a constructive proof that primality detection is in P as opposed to many great proofs that are unfortunately nonconstructive.

its interconnected to the RSA cryptography algorithm mentioned in another answer because that algorithm needs to find large primes quickly, prior to the AKS algorithm this was only probabilistically possible. its fundamentally connected to number theory & other deep problems eg the Riemann conjecture which in many ways is the original realm of algorithmics.

awarded the 2006 Gödel Prize and the 2006 Fulkerson Prize

> **Comments:**
> **username_1**: This is definitely an important result, but beautiful?  Really?  
> **username_0**: I agree with the above comment by JeffE. The result is vastly significant and thats what has been pointed out in the answer, rather than how (or what idea(s) used in) AKS primality testing is/are beautiful.  
> **username_12**: to me a "vastly significant" result is beautiful. "your mileage may vary".  
> **username_20**: Miller-Rabin is quite beautiful, on the other hand  
> **username_12**: dont know why people would consider the probabilistic algorithm superior in beauty to the exact algorithm. yes, AKS is largely based on [Miller-Rabin](http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test) but is major advance removing the randomization that was missed (or maybe not seen as possible) for decades & finally found. to me thats beautiful. moreover number theory is just a beautiful area of mathematics/algorithmics [with the theory of primes starring in number theory], this perspective can be seen in eg the famous book Mathematicians Apology by GH Hardy.  

---

### Answer by username_4 on 2012-02-27. Score: 9

There are lots of lovely results about probabilistic algorithms, which are deceptively simple and a great step forward in the way we think about computation.

von Neumann's trick for implementing a fair coin with a biased one. We are so used to probabilistic algorithms now, but from an outside perspective, this is unbelieveably cool. Both the algorithm and proof are accessible to anyone who knows high-school probability.

> **Comments:**
> **username_14**: I would have expected you to mention Yao's minmax principle for finding lower bounds on the expected running times of Las Vegas algorithms. It connects ideas of game theory with probability and algorithms.  
> **username_4**: Sure. But I'm spamming this question with enough answers already. Please add your favourite result as an answer.  

---

### Answer by username_4 on 2012-02-27. Score: 9

One of my favourite family of results is that various problems of a seemingly infinite nature are decidable.

1. The first order theory of real closed fields is decidable (by Tarski). Euclidean geometry is also a model of the axioms of real-closed fields, hence, by Tarski, first order statements in this model are decidable.
2. Presburger arithmetic is decidable.
3. First order theory of algebraically closed fields (this includes complex numbers) is decidable.
4. Monadic second order logic over infinite (and finite) words is decidable. The proof is elegant and can be taught to undergrads.


---

### Answer by username_23 on 2012-02-28. Score: 8

The result by Tim Griffin that control operators such as `call/cc` are related to classical logic, extending the Curry-Howard correspondence.

Basically, the typing of `call/cc` is such that if $E$ has type $\neg\neg \tau$, then $\mathtt{call/cc}{(E)}$ has type $\tau$. This works out when interpreting the type $\neg\tau$ as $\tau\rightarrow\bot$, as is standard in logic, and corresponds to the type of a function that takes a $\tau$ and never returns. That's exactly what a continuation does, making the correspondence work.

His [paper](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.6893), "A Formulae-as-types notion of control", appears in POPL 1990.


---

### Answer by username_24 on 2012-02-29. Score: 7

My favorite is Rabin's linear time algorithm for computing the closest pair of points in the plane (or more precisely its simplification). It get across the importance of the computation model, the power of randomized algorithms, and some elegant way to think about randomized algorithms.

This said, CS is still far from achieving the level of elegance one encounters in mathematics (well, they had 5000 years head start), from basic definitions/results in calculus, topology (fixed point theorems), combinatorics, geometry (Pythagorean theorem <http://en.wikipedia.org/wiki/File:Pythag_anim.gif>), etc.

If you look for beauty, look for it everywhere...


---

### Answer by username_25 on 2012-02-27. Score: 5

This result is probably a bit recent to qualify as fundamental, but I believe that the *types-as-homotopy-types* interpretation qualifies. This view allows interpreting types from [constructive type theory](http://en.wikipedia.org/wiki/Intuitionistic_type_theory) as sets with certain geometric properties, in this case [homotopy](http://en.wikipedia.org/wiki/Homotopy).

I find this point of view to be particularly beautiful as it makes certain previously complex observations about type theory simple, for instance the fact that["axiom K" is not derivable](http://homotopytypetheory.org/2011/04/10/just-kidding-understanding-identity-elimination-in-homotopy-type-theory/).

An overview of this budding field by Steve Awodey can be found [here](http://www.andrew.cmu.edu/user/awodey/preprints/TTH.pdf).


---

### Answer by username_26 on 2014-05-14. Score: 3

[Zero-knowledge proof](http://en.wikipedia.org/wiki/Zero-knowledge_proof) is a very interesting concept. It allows for an entity, the prover, to prove (with high probability) to another entity, the verifier, that it knows "a secret" (a solution to some NP-problem, a modular square-root of some number, a discrete log of some number etc …) without giving any information at all about the secret (which is difficult at first glance, since the first idea for proving that you know a secret is to actually tell the secret, and that any communication that could result in the verifier believing that you know the secret can a priori only increase the knowledge of the verifier about the secret).


---

