<p>A family of counter-intuitive results is the whole "prove an upper bound to prove a lower bound" family of results. The Meyer result that $\mathsf{P} = \mathsf{NP}$ implies $\mathsf{EXP} \not\subseteq \mathsf{P}/poly$ is one example of this, and this came to my mind from both Ketan Mulmuley's GCT work as well as Ryan Williams' recent result that again used an upper bound for CIRCUIT-SAT to prove a <em>lower bound</em> for $\mathsf{NEXP}$ in terms of $\mathsf{ACC}$. </p>

CC BY-SA 2.5
2010-11-29T05:19:14.297Z
Suresh, Please provide reference to Meyer's result.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-29T06:50:08.930Z
I don't know if there's a direct reference. The Karp-Lipton paper (http://faculty.cs.tamu.edu/chen/courses/637/2008/pres/ashraf.pdf) credits Meyer with this result, but there's no citation.
Suresh Venkat
CC BY-SA 2.5
2010-11-12T06:20:48.770Z
2010-11-12T06:20:48.770Z
Suresh Venkat
<p>SAT has a polynomial-time algorithm only if P=NP. We don't know whether P=NP. However, I can write down an algorithm for SAT which is polynomial-time if P=NP is true. I don't know the correct reference for this, but the <a href="http://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-time_algorithms">wikipedia page</a> gives such an algorithm and credits Levin.</p>

CC BY-SA 2.5
2010-11-23T04:43:40.543Z
This is typically referred to as "Levin universal search," and the correct reference is: L. Levin, Universal enumeration problems. Problems of Information Transmission, 9(3):265--266, 1973 (translated from Russian). This is the same paper in which Levin introduced NP-completeness (see also Cook & Karp, but as far as I know neither of them introduced the notion of an optimal universal search algorithm). The English translation can be found in Trakhtenbrot's famous survey: http://doi.ieeecomputersociety.org/10.1109/MAHC.1984.10036
Joshua Grochow
CC BY-SA 2.5
2010-11-12T05:11:57.410Z
Similarly, we have a provably optimal algorithm for factoring that runs in polynomial time if factoring is in P, yet we do not know if factoring is in P (or how to analyze the runtime of this optimal function).
Ross Snider
CC BY-SA 2.5
2010-11-11T03:16:29.600Z
2010-11-11T03:16:29.600Z
mikero
<p>One surprising and counter intuitive result is that $IP = PSPACE$, proved using arithmetization around 1990.</p>

<p>As Arora &amp; Barak put it (p. 157) "We know that interaction alone does not give us any languages outside NP. We also suspect that randomization alone does not add significant power to computation. So how much power could the combination of randomization and interaction provide?"</p>

<p>Apparently quite a bit!</p>

CC BY-SA 2.5
2010-11-23T08:40:01.073Z
2010-11-23T08:40:01.073Z
Huck Bennett
<p>Computability certainly screws most students. A beautiful example with high confusion rate is this:</p>

<p>$f(n) := \begin{cases}1, \quad \pi \text{ has } 0^n \text{ in its decimals} \\\\ 0, \quad else\end{cases}$</p>

<p>Is $f$ computable?</p>

<p>The answer is yes; see a discussion <a href="https://cstheory.stackexchange.com/questions/1977/false-proof-for-computability-of-a-function">here</a>. Most people immediately try constructing $f$ with present knowledge. That can not work and leads to a perceived paradox which is really just subtleness.</p>

CC BY-SA 2.5
2010-11-11T03:56:47.053Z
This to me seems like one of those problems where all of its trickiness is in how it's stated. This reminds me a bit of taking an algorithm, fiating that n is some constant and proclaiming that the algorithm now runs in constant time. The hard question people will typically think you're asking is whether we can write a program that will either prove pi contains a 0^n string for all n or that will determine the largest n for which it is true.
Joseph Garvin
CC BY-SA 2.5
2010-11-11T09:08:19.930Z
Sure, but the fact they think like that does not illustrate trickiness the function's formulation but that people do not understand the difference between existence and construction.
Raphael
CC BY-SA 2.5
2010-11-09T22:30:25.077Z
2010-11-09T22:30:25.077Z
2017-04-13T12:32:28.743Z
Raphael
<p>I find the fact that network flow is polynomial time counter intuitive. It is seems much harder on first look than many NP-Hard problems. Or putting it differently, there are many results in CS where the running time to solve them is way better than what you would expect it to be.</p>

CC BY-SA 2.5
2010-11-12T06:16:33.157Z
ditto: I've had students comment on the non-intuitveness of network flow, and even the fact that matchings can be done in poly time seems highly surprising.
Suresh Venkat
CC BY-SA 3.0
2012-10-20T01:56:32.663Z
I don't quite agree. Network flow can be easily reduced to linear programming so you are claiming that linear programming being in P is counterintuitive. Perhaps. But duality shows that LP is in NP and co-NP which at least suggests that it may not be that hard. What is less intuitive is that min-cut is solvable in P because it is not naturally a "fractional" problem.
Chandra Chekuri
CC BY-SA 2.5
2010-11-12T05:08:32.140Z
2010-11-12T05:08:32.140Z
Sariel Har-Peled
<p>How about Martin Escardo's publications showing that there are infinite sets that can be exhaustively searched over in finite time?  See Escardo's guest blog post on Andrej Bauer's blog, for instance, on <a href="http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/">"Seemingly impossible functional programs"</a>.</p>

CC BY-SA 2.5
2010-11-25T19:29:22.080Z
2010-11-25T19:29:22.080Z
Dominic Mulligan
<p>The Recursion Theorem certainly seems counter-intuitive the first time you see it. Essentially it says that when you are describing a Turing Machine, you can assume it has access to its own description. In other words, I can build Turing Machines like:</p>

<p>TM M accepts n iff n is a multiple of the number of times "1" appears in the string representation of M.</p>

<p>TM N takes in a number n and outputs n copies of itself.</p>

<p>Note that the "string representation" here is not referring to the informal text description, but rather an encoding.</p>

CC BY-SA 2.5
2010-11-10T17:22:17.517Z
2010-11-10T17:22:17.517Z
Mark Reitblatt
<p>As Philip said, Rice's theorem is a good example: one's intuition before studying computability is that there must surely be <em>something</em> we can compute about computations. It turns out that we can only compute something about <em>some</em> computations.</p>

CC BY-SA 2.5
2010-11-23T00:34:42.113Z
2010-11-23T00:34:42.113Z
Max
<p>How about the fact that computing permanent is #P-Complete but computing determinant - a way weirder operation happens to be in the class NC?</p>

<p>This seems rather strange - it did not have to be that way (or maybe it did ;-) )</p>

CC BY-SA 2.5
2010-11-26T02:07:58.417Z
2010-11-26T02:07:58.417Z
Akash Kumar
<p>Proving information-theoretic results based on complexity-theoretic assumptions is another counter-intuitive result. For instance, Bellare <em>et al.</em> in their paper <a href="http://portal.acm.org/citation.cfm?id=100285">The (True) Complexity of Statistical Zero Knowledge</a> <strong>constructively</strong> proved that, under the <strong>certified discrete log assumption</strong>, any language that admits <em>honest-verifier</em> statistical zero knowledge also admits statistical zero knowledge.</p>

<p>The result was so odd that it surprise the authors. They pointed out this fact several times; for instance, in the introduction:</p>

<blockquote>
  <p>Given  that  statistical  zero-knowledge  is  a  computationally  independent  notion,  it  is somewhat  strange  that properties  about  it  could  be  proved  under  a  computational  intractability  assumption.</p>
</blockquote>

<p><strong>PS:</strong> A stronger result was later proved unconditionally by Okamoto (<a href="http://dx.doi.org/10.1006/jcss.1999.1664">On Relationships between Statistical Zero-Knowledge Proofs</a>).</p>

<h3>Description of some terms</h3>

<p>Since the above result includes a lot of cryptographic jargon, I try to informally define each term.</p>

<ol>
<li><em>Certified discrete log assumption:</em> It is hard (for poly-size circuits) to solve the discrete logarithm, even if the group prime ($p$) is certified; that is, the factorization of $p-1$ is given.</li>
<li><em>Zero knowledge</em>: A protocol which yields no knowledge to polynomial-time bounded parties.</li>
<li><em>Statistical zero knowledge:</em> A protocol which yields no information, even to computationally unbounded parties, except with negligible probability.</li>
<li><em>Honest-verifier zero knowledge:</em> A protocol which yields no knowledge to polynomial-time bounded parties, <strong>if</strong> they act as specified by protocol.</li>
</ol>

CC BY-SA 2.5
2010-11-21T19:03:51.393Z
2010-11-21T19:03:51.393Z
Sadeq Dousti
<p>The linear programming problem is solvable in (weakly) polynomial time. This seems very surprising: why would we be able to find one among an exponential number of vertices of a high-dimensional polytope? Why would we be able to solve a problem which is so ridiculously expressive? </p>

<p>Not to mention all the exponential-size linear programs which we can solved by using the ellipsoid method and separation oracles, and other methods (adding variables, etc.). For example, it's amazing that an LP with an exponential number of variables such as the Karmakar-Karp relaxation of Bin Packing can be efficiently approximated.</p>

CC BY-SA 3.0
2012-10-20T18:31:39.540Z
The fact that there are exponential number of solutions is not unique to LP. Most discrete optimization problems have the same feature but they have poly-time algorithms, no? LP is a special case of convex optimization where a local optimum is a global optimum. We can also solve convex optimization modulo an epsilon issue due to irrationality and other technical reasons. For LP, due to the combinatorial structure, one can jump from this small error solution to a vertex which gives an exact solution. Equivalence of separation and optimization is surprising though.
Chandra Chekuri
CC BY-SA 3.0
2012-10-21T02:33:01.037Z
@ChandraChekuri what I had in mind is that a high-dimensional geometric search problem sounds like it should be hard..but of course there are also good reasons why it's not (convexity). I should probably emphasize the equivalence of separation and optimization instead. Plenty of surprising consequences there, like solving hard optimization problems on perfect graphs, for example.
Sasho Nikolov
CC BY-SA 3.0
2012-10-20T00:11:00.040Z
2012-10-20T00:11:00.040Z
Sasho Nikolov
<p>Whenever I teach automata, I always ask my students if they find it surprising that nondeterminism doesn't add any power to finite-state automata (i.e., that for every NFA is there is an equivalent -- possibly much larger -- DFA). About half the class reports being surprised, so there you go. [I myself have lost the "feel" for what is surprising at the intro level.]</p>

<p>Students definitely find it surprising at first that $R\neq RE$. I challenge them to produce an algorithm that determines whether a given java program will halt, and they typically try to search for endless while loops. As soon as I show them ways of constructing loops whose termination is far from obvious, the surprise factor goes away.</p>

CC BY-SA 3.0
2016-05-30T18:55:17.800Z
2016-05-30T18:55:17.800Z
Aryeh
<p>I have found the <a href="http://www.springerlink.com/index/G9N5V2MNV1L99YDR.pdf" rel="nofollow">A simple public-key cryptosystem with a double trapdoor decryption mechanism and its applications</a> paradoxical, because it is a adaptive chosen ciphertext secure scheme which is homomorphic.</p>

CC BY-SA 2.5
2010-11-23T09:04:41.253Z
2010-11-23T09:04:41.253Z
Yasser Sobhdel
<p>Some math and logic paradoxes could be automatically applied to computers probably, but are there any paradoxes that were discovered in computer science itself?</p>

<p>By paradoxes I mean counter intuitive results that look like a contradiction.</p>

CC BY-SA 2.5
2010-11-25T20:24:40.030Z
Counterintuitiveness is a function of time. The fact that so many different questions are all NP-complete was undoubtedly counterintuitive before Karp's paper, as was the fact that channels have definite information capacities before Shannon's. However, now people are used to these results.
Peter Shor 
CC BY-SA 2.5
2010-11-08T21:18:42.247Z
maybe someone could tag it properly...
serg
CC BY-SA 2.5
2010-11-08T21:46:45.673Z
Are you looking for things that feel paradox or real inconsistencies (e.g. Russell's paradox)?
Raphael
CC BY-SA 2.5
2010-11-08T22:49:57.777Z
I don't know a suitable tag for this question, maybe [big-picture] or [soft-question]. Can you give an example of math paradoxes you have mentioned so we can know what you are talking about?
Kaveh
CC BY-SA 2.5
2010-11-09T03:38:16.257Z
Obviously, there aren't any known inconsistencies in computer science---that would be worrying. Are you just looking for counterintuitive results? Are results like the PCP theorem, Kleene's recursion theorem, and public key cryptosystems bizarre enough to count as paradoxes to you?
Thomas Steinke
CC BY-SA 2.5
2010-11-09T04:19:10.697Z
@serg, it would be really helpful if you could respond to clarify your question. Either you mean your question in a very "soft" sense that Thomas suggests - in which case the question is correctly tagged as big-picture and my answer below is off-topic, or you mean it in a somewhat technical sense ("applications and impacts of logical paradoxes in computer science") in which case your question should be tagged lo.logic, not big-picture. Or you mean something else entirely that we four commenters haven't guessed!
Rob Simmons
CC BY-SA 2.5
2010-11-09T22:05:57.970Z
@Rob I meant it in a soft sense as Thomas mentioned, so "big picture" seems good choice. Your answer is great though, don't delete it. Sorry for misunderstanding.
serg
CC BY-SA 2.5
2010-11-09T22:12:02.677Z
The word “paradox” means different things depending on context.  If “paradox” in your question means a counterintuitive result, please edit the question to clarify it.  (I think that it is the best to avoid using the word “paradox”.)  The current wording of the question is very unclear.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-09T22:27:11.090Z
Reading the question in revision 4, I retagged it from [big-picture] to [big-list] and flagged it to ask moderators to make the question community-wiki.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-10T08:25:42.277Z
@serg: could you please edit the title and replace it with something like "counterintuitive results in theoretical computer science"? I think you will get much more views and better answers if you avoid using the word "paradox" in the title.
Kaveh
CC BY-SA 2.5
2010-11-11T12:31:01.930Z
See the question http://cstheory.stackexchange.com/questions/276/surprising-results-in-complexity-not-on-the-complexity-blog-list which posed essentially the same question with a complexity angle.
András Salamon
<big-list>
Are there any counterintuitive results in theoretical computer science?
serg
# Are there any counterintuitive results in theoretical computer science?

(Asked by: username_0 on 2010-11-08)

Some math and logic paradoxes could be automatically applied to computers probably, but are there any paradoxes that were discovered in computer science itself?

By paradoxes I mean counter intuitive results that look like a contradiction.

**Tags:** big-list
> **Comments:**
> **username_0**: maybe someone could tag it properly...  
> **username_2**: Are you looking for things that feel paradox or real inconsistencies (e.g. Russell's paradox)?  
> **username_3**: I don't know a suitable tag for this question, maybe [big-picture] or [soft-question]. Can you give an example of math paradoxes you have mentioned so we can know what you are talking about?  
> **username_4**: Obviously, there aren't any known inconsistencies in computer science---that would be worrying. Are you just looking for counterintuitive results? Are results like the PCP theorem, Kleene's recursion theorem, and public key cryptosystems bizarre enough to count as paradoxes to you?  
> **username_5**: @serg, it would be really helpful if you could respond to clarify your question. Either you mean your question in a very "soft" sense that Thomas suggests - in which case the question is correctly tagged as big-picture and my answer below is off-topic, or you mean it in a somewhat technical sense ("applications and impacts of logical paradoxes in computer science") in which case your question should be tagged lo.logic, not big-picture. Or you mean something else entirely that we four commenters haven't guessed!  
> **username_0**: @Rob I meant it in a soft sense as Thomas mentioned, so "big picture" seems good choice. Your answer is great though, don't delete it. Sorry for misunderstanding.  
> **username_6**: The word “paradox” means different things depending on context.  If “paradox” in your question means a counterintuitive result, please edit the question to clarify it.  (I think that it is the best to avoid using the word “paradox”.)  The current wording of the question is very unclear.  
> **username_6**: Reading the question in revision 4, I retagged it from [big-picture] to [big-list] and flagged it to ask moderators to make the question community-wiki.  
> **username_3**: @serg: could you please edit the title and replace it with something like "counterintuitive results in theoretical computer science"? I think you will get much more views and better answers if you avoid using the word "paradox" in the title.  
> **username_7**: See the question http://cstheory.stackexchange.com/questions/276/surprising-results-in-complexity-not-on-the-complexity-blog-list which posed essentially the same question with a complexity angle.  
> **username_1**: Counterintuitiveness is a function of time. The fact that so many different questions are all NP-complete was undoubtedly counterintuitive before Karp's paper, as was the fact that channels have definite information capacities before Shannon's. However, now people are used to these results.  

---

## 13 answers

### Answer by username_15 on 2010-11-12. Score: 28

I find the fact that network flow is polynomial time counter intuitive. It is seems much harder on first look than many NP-Hard problems. Or putting it differently, there are many results in CS where the running time to solve them is way better than what you would expect it to be.

> **Comments:**
> **username_8**: ditto: I've had students comment on the non-intuitveness of network flow, and even the fact that matchings can be done in poly time seems highly surprising.  
> **username_16**: I don't quite agree. Network flow can be easily reduced to linear programming so you are claiming that linear programming being in P is counterintuitive. Perhaps. But duality shows that LP is in NP and co-NP which at least suggests that it may not be that hard. What is less intuitive is that min-cut is solvable in P because it is not naturally a "fractional" problem.  

---

### Answer by username_8 on 2010-11-12. Score: 22

A family of counter-intuitive results is the whole "prove an upper bound to prove a lower bound" family of results. The Meyer result that $\mathsf{P} = \mathsf{NP}$ implies $\mathsf{EXP} \not\subseteq \mathsf{P}/poly$ is one example of this, and this came to my mind from both Ketan Mulmuley's GCT work as well as Ryan Williams' recent result that again used an upper bound for CIRCUIT-SAT to prove a *lower bound* for $\mathsf{NEXP}$ in terms of $\mathsf{ACC}$.

> **Comments:**
> **username_9**: Suresh, Please provide reference to Meyer's result.  
> **username_8**: I don't know if there's a direct reference. The Karp-Lipton paper (http://faculty.cs.tamu.edu/chen/courses/637/2008/pres/ashraf.pdf) credits Meyer with this result, but there's no citation.  

---

### Answer by username_10 on 2010-11-11. Score: 20

SAT has a polynomial-time algorithm only if P=NP. We don't know whether P=NP. However, I can write down an algorithm for SAT which is polynomial-time if P=NP is true. I don't know the correct reference for this, but the [wikipedia page](http://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-time_algorithms) gives such an algorithm and credits Levin.

> **Comments:**
> **username_12**: Similarly, we have a provably optimal algorithm for factoring that runs in polynomial time if factoring is in P, yet we do not know if factoring is in P (or how to analyze the runtime of this optimal function).  
> **username_11**: This is typically referred to as "Levin universal search," and the correct reference is: L. Levin, Universal enumeration problems. Problems of Information Transmission, 9(3):265--266, 1973 (translated from Russian). This is the same paper in which Levin introduced NP-completeness (see also Cook & Karp, but as far as I know neither of them introduced the notion of an optimal universal search algorithm). The English translation can be found in Trakhtenbrot's famous survey: http://doi.ieeecomputersociety.org/10.1109/MAHC.1984.10036  

---

### Answer by username_13 on 2010-11-23. Score: 18

One surprising and counter intuitive result is that $IP = PSPACE$, proved using arithmetization around 1990.

As Arora & Barak put it (p. 157) "We know that interaction alone does not give us any languages outside NP. We also suspect that randomization alone does not add significant power to computation. So how much power could the combination of randomization and interaction provide?"

Apparently quite a bit!


---

### Answer by username_2 on 2010-11-09. Score: 18

Computability certainly screws most students. A beautiful example with high confusion rate is this:

$f(n) := \begin{cases}1, \quad \pi \text{ has } 0^n \text{ in its decimals} \\\\ 0, \quad else\end{cases}$

Is $f$ computable?

The answer is yes; see a discussion [here](https://cstheory.stackexchange.com/questions/1977/false-proof-for-computability-of-a-function). Most people immediately try constructing $f$ with present knowledge. That can not work and leads to a perceived paradox which is really just subtleness.

> **Comments:**
> **username_14**: This to me seems like one of those problems where all of its trickiness is in how it's stated. This reminds me a bit of taking an algorithm, fiating that n is some constant and proclaiming that the algorithm now runs in constant time. The hard question people will typically think you're asking is whether we can write a program that will either prove pi contains a 0^n string for all n or that will determine the largest n for which it is true.  
> **username_2**: Sure, but the fact they think like that does not illustrate trickiness the function's formulation but that people do not understand the difference between existence and construction.  

---

### Answer by username_17 on 2010-11-25. Score: 14

How about Martin Escardo's publications showing that there are infinite sets that can be exhaustively searched over in finite time? See Escardo's guest blog post on Andrej Bauer's blog, for instance, on ["Seemingly impossible functional programs"](http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/).


---

### Answer by username_18 on 2010-11-10. Score: 13

The Recursion Theorem certainly seems counter-intuitive the first time you see it. Essentially it says that when you are describing a Turing Machine, you can assume it has access to its own description. In other words, I can build Turing Machines like:

TM M accepts n iff n is a multiple of the number of times "1" appears in the string representation of M.

TM N takes in a number n and outputs n copies of itself.

Note that the "string representation" here is not referring to the informal text description, but rather an encoding.


---

### Answer by username_19 on 2010-11-23. Score: 13

As Philip said, Rice's theorem is a good example: one's intuition before studying computability is that there must surely be *something* we can compute about computations. It turns out that we can only compute something about *some* computations.


---

### Answer by username_20 on 2010-11-26. Score: 11

How about the fact that computing permanent is #P-Complete but computing determinant - a way weirder operation happens to be in the class NC?

This seems rather strange - it did not have to be that way (or maybe it did ;-) )


---

### Answer by username_21 on 2010-11-21. Score: 11

Proving information-theoretic results based on complexity-theoretic assumptions is another counter-intuitive result. For instance, Bellare *et al.* in their paper [The (True) Complexity of Statistical Zero Knowledge](http://portal.acm.org/citation.cfm?id=100285) **constructively** proved that, under the **certified discrete log assumption**, any language that admits *honest-verifier* statistical zero knowledge also admits statistical zero knowledge.

The result was so odd that it surprise the authors. They pointed out this fact several times; for instance, in the introduction:

> Given that statistical zero-knowledge is a computationally independent notion, it is somewhat strange that properties about it could be proved under a computational intractability assumption.

**PS:** A stronger result was later proved unconditionally by Okamoto ([On Relationships between Statistical Zero-Knowledge Proofs](http://dx.doi.org/10.1006/jcss.1999.1664)).

### Description of some terms

Since the above result includes a lot of cryptographic jargon, I try to informally define each term.

1. *Certified discrete log assumption:* It is hard (for poly-size circuits) to solve the discrete logarithm, even if the group prime ($p$) is certified; that is, the factorization of $p-1$ is given.
2. *Zero knowledge*: A protocol which yields no knowledge to polynomial-time bounded parties.
3. *Statistical zero knowledge:* A protocol which yields no information, even to computationally unbounded parties, except with negligible probability.
4. *Honest-verifier zero knowledge:* A protocol which yields no knowledge to polynomial-time bounded parties, **if** they act as specified by protocol.


---

### Answer by username_22 on 2012-10-20. Score: 7

The linear programming problem is solvable in (weakly) polynomial time. This seems very surprising: why would we be able to find one among an exponential number of vertices of a high-dimensional polytope? Why would we be able to solve a problem which is so ridiculously expressive?

Not to mention all the exponential-size linear programs which we can solved by using the ellipsoid method and separation oracles, and other methods (adding variables, etc.). For example, it's amazing that an LP with an exponential number of variables such as the Karmakar-Karp relaxation of Bin Packing can be efficiently approximated.

> **Comments:**
> **username_16**: The fact that there are exponential number of solutions is not unique to LP. Most discrete optimization problems have the same feature but they have poly-time algorithms, no? LP is a special case of convex optimization where a local optimum is a global optimum. We can also solve convex optimization modulo an epsilon issue due to irrationality and other technical reasons. For LP, due to the combinatorial structure, one can jump from this small error solution to a vertex which gives an exact solution. Equivalence of separation and optimization is surprising though.  
> **username_22**: @ChandraChekuri what I had in mind is that a high-dimensional geometric search problem sounds like it should be hard..but of course there are also good reasons why it's not (convexity). I should probably emphasize the equivalence of separation and optimization instead. Plenty of surprising consequences there, like solving hard optimization problems on perfect graphs, for example.  

---

### Answer by username_23 on 2016-05-30. Score: 4

Whenever I teach automata, I always ask my students if they find it surprising that nondeterminism doesn't add any power to finite-state automata (i.e., that for every NFA is there is an equivalent -- possibly much larger -- DFA). About half the class reports being surprised, so there you go. [I myself have lost the "feel" for what is surprising at the intro level.]

Students definitely find it surprising at first that $R\neq RE$. I challenge them to produce an algorithm that determines whether a given java program will halt, and they typically try to search for endless while loops. As soon as I show them ways of constructing loops whose termination is far from obvious, the surprise factor goes away.


---

### Answer by username_24 on 2010-11-23. Score: 1

I have found the [A simple public-key cryptosystem with a double trapdoor decryption mechanism and its applications](http://www.springerlink.com/index/G9N5V2MNV1L99YDR.pdf) paradoxical, because it is a adaptive chosen ciphertext secure scheme which is homomorphic.


---

