<p>If $P \neq NP$, then there is a "diagonalization" proof for it.</p>

<p>This result is due to Kozen. Not everyone agrees with what he calls a "diagonalization" proof.</p>

CC BY-SA 3.0
2012-07-16T20:28:45.410Z
how does this relate to the Baker Gill Solovay 1975 result?
vzn
CC BY-SA 2.5
2010-08-19T21:37:05.817Z
This was very supervising for me because I had heard many times that diagonalization cannot seprate $NP$ from $P$.
Kaveh
CC BY-SA 2.5
2010-08-22T17:00:22.560Z
Can you give a reference?  I have not heard of this result previously, but it sounds very interesting.  Particularly as it stands in stark contrast with my intuition that relativization rules out what I generally think of as diagonalization proofs...
Joshua Grochow
CC BY-SA 2.5
2010-08-22T17:55:53.220Z
D. Kozen, "Indexing of subrecursive classes", 1978
Kaveh
CC BY-SA 2.5
2010-08-19T21:35:02.150Z
2010-08-19T21:35:02.150Z
Kaveh
<p>At Barriers I, a panel of leading complexity theorists agreed that Barrington's Theorem was the result that most surprised them.  Fortnow explains Barrington's Theorem here: <a href="http://blog.computationalcomplexity.org/2008/11/barringtons-theorem.html">http://blog.computationalcomplexity.org/2008/11/barringtons-theorem.html</a></p>

CC BY-SA 2.5
2010-08-18T18:31:40.570Z
2010-08-18T22:41:58.790Z
2010-08-18T22:41:58.790Z
Aaron Sterling
<p>$NL$ is closed under complementation.</p>

CC BY-SA 2.5
2010-08-19T21:45:08.627Z
2010-08-19T21:45:08.627Z
Kaveh
<p>I would say the recent work of Jain, Upadhyay and Watrous showing that QIP = IP = PSPACE is quite surprising. My opinion is that it isn't so much that QIP = IP is interesting but rather the fact that all of QIP can be simulated in a 3 round quantum interactive proof. A rather cool demonstration of the power of quantum parallelism.</p>

<p>Something that continues to surprise me is that BPP is likely to be P - It brings up a lot of philosophical questions regarding the nature of randomness.</p>

CC BY-SA 2.5
2010-09-11T02:30:03.920Z
QIP = QIP(3) has been known for about 10 years now. The QIP = PSPACE paper did not show that.
Robin Kothari
CC BY-SA 2.5
2010-12-08T23:41:30.713Z
The recent result QIP=PSPACE is by Jain, Ji, Upadhyay and Watrous.
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-21T21:45:51.437Z
2010-08-21T21:45:51.437Z
Henry Yuen
<p><a href="http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems">Gödel's incompleteness theorems</a></p>

CC BY-SA 2.5
2010-08-19T09:59:21.510Z
2010-08-19T09:59:21.510Z
ripper234
<p>Razborov-Rudich Natural Proofs theorem.</p>

<p>(AFAIK) People were very hopeful about proving circuit lower bounds but after this theorem many stopped working and moved to other topics.</p>

CC BY-SA 2.5
2010-08-19T21:41:24.010Z
2010-08-19T21:41:24.010Z
Kaveh
<p><i>The counting version of the Monotone-SAT problem is #P-complete.</i></p>

<p>A Monotone-SAT instance is a propositional formula $F$ with the following restriction: every variable either always occurs positive or always occurs negative (in other words, every literal in $F$ is a pure literal).</p>

<p>I was very surprised by this result, because the decision version of the Monotone-SAT problem is trivial.</p>

<p>It's widely known that there exist decision problems in P whose counting versions are #P-complete (one example is 2-SAT). But this case is a bit "different" in my opinion: finding a satisfying assignment of a Monotone-SAT instance is not only easy (as, for example, finding a satisfying assignment of a 2-SAT instance), it's dramatically trivial. Not just easy: trivial, literally. Note that given, say, a 2-SAT instance, it can be either satisfiable or unsatisfiable of course; while given a Monotone-SAT instance you know in advance that it is certainly satisfiable: it cannot be unsatisfiable, no way: this confirms that, even both problems are easy, their levels of "decision-easiness" are different. On the other hand, their levels of "counting-uneasiness" is exactly the same.</p>

<p>This strong contrast between the following facts</p>

<ol>
<li>Deciding Monotone-SAT is dumb-trivial</li>
<li>Counting Monotone-SAT is extremely-hard</li>
</ol>

<p>is IMHO at least fascinating.</p>

CC BY-SA 2.5
2010-09-09T10:28:18.927Z
2010-10-06T14:17:51.620Z
2010-10-06T14:17:51.620Z
Giorgio Camerani
<p>That the axioms of <a href="http://en.wikipedia.org/wiki/Axiom_of_choice" rel="noreferrer">Choice</a> and <a href="http://en.wikipedia.org/wiki/Axiom_of_determinacy" rel="noreferrer">Determinacy</a> are not compatible.</p>

CC BY-SA 2.5
2010-08-19T09:57:58.017Z
2010-08-19T09:57:58.017Z
ripper234
<p>Here is the guest post by Bill Gasarch with help from Harry Lewis and Richard Ladner:
<a href="http://blog.computationalcomplexity.org/2005/12/surprising-results.html">http://blog.computationalcomplexity.org/2005/12/surprising-results.html</a></p>

CC BY-SA 2.5
2010-08-18T18:21:53.650Z
wow I somehow missed this!  Probably no need for us to make a list then :)
Lev Reyzin
CC BY-SA 2.5
2010-08-18T19:20:00.113Z
Perhaps it would be good to focus on surprising results since 2005 here.
Jukka Suomela
CC BY-SA 2.5
2010-08-18T18:20:33.853Z
2010-08-18T18:20:33.853Z
Zeyu
<p>What were the most surprising results in complexity?</p>

<p>I think it would be useful to have a list of unexpected/surprising results.  This includes both results that were surprising and came out of nowhere and also results that turned out different than people expected.</p>

<p><b>Edit</b>: <i>given the <b><a href="http://blog.computationalcomplexity.org/2005/12/surprising-results.html">list</a></b> by Gasarch, Lewis, and Ladner on the complexity blog (pointed out by @Zeyu), let's focus this community wiki on results not on their list.</i>  Perhaps this will lead to a focus on results after 2005 (as per @Jukka's suggestion).</p>

<p>An example: <b>Weak Learning = Strong Learning [Schapire 1990]</b>: (Surprisingly?) Having any edge over random guessing gets you PAC learning. Lead to the AdaBoost algorithm.</p>

CC BY-SA 2.5
2010-08-18T18:14:45.567Z
I realize that this may be out-of-scope, but it's good to check the boundaries in beta, right? :)
Lev Reyzin
CC BY-SA 2.5
2010-08-18T19:16:50.543Z
Certainly on-topic, I would say.
Jukka Suomela
<cc.complexity-theory><big-list>
Surprising Results in Complexity (Not on the Complexity Blog List)
Lev Reyzin
# Surprising Results in Complexity (Not on the Complexity Blog List)

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

What were the most surprising results in complexity?

I think it would be useful to have a list of unexpected/surprising results. This includes both results that were surprising and came out of nowhere and also results that turned out different than people expected.

**Edit**: *given the **[list](http://blog.computationalcomplexity.org/2005/12/surprising-results.html)** by Gasarch, Lewis, and Ladner on the complexity blog (pointed out by @Zeyu), let's focus this community wiki on results not on their list.* Perhaps this will lead to a focus on results after 2005 (as per @Jukka's suggestion).

An example: **Weak Learning = Strong Learning [Schapire 1990]**: (Surprisingly?) Having any edge over random guessing gets you PAC learning. Lead to the AdaBoost algorithm.

**Tags:** cc.complexity-theory, big-list
> **Comments:**
> **username_0**: I realize that this may be out-of-scope, but it's good to check the boundaries in beta, right? :)  
> **username_1**: Certainly on-topic, I would say.  

---

## 9 answers

### Answer by username_11 on 2010-08-18. Score: 29 | Accepted answer

Here is the guest post by Bill Gasarch with help from Harry Lewis and Richard Ladner:
<http://blog.computationalcomplexity.org/2005/12/surprising-results.html>

> **Comments:**
> **username_0**: wow I somehow missed this!  Probably no need for us to make a list then :)  
> **username_1**: Perhaps it would be good to focus on surprising results since 2005 here.  

---

### Answer by username_2 on 2010-08-19. Score: 21

If $P \neq NP$, then there is a "diagonalization" proof for it.

This result is due to Kozen. Not everyone agrees with what he calls a "diagonalization" proof.

> **Comments:**
> **username_2**: This was very supervising for me because I had heard many times that diagonalization cannot seprate $NP$ from $P$.  
> **username_4**: Can you give a reference?  I have not heard of this result previously, but it sounds very interesting.  Particularly as it stands in stark contrast with my intuition that relativization rules out what I generally think of as diagonalization proofs...  
> **username_2**: D. Kozen, "Indexing of subrecursive classes", 1978  
> **username_3**: how does this relate to the Baker Gill Solovay 1975 result?  

---

### Answer by username_5 on 2010-08-18. Score: 19

At Barriers I, a panel of leading complexity theorists agreed that Barrington's Theorem was the result that most surprised them. Fortnow explains Barrington's Theorem here: <http://blog.computationalcomplexity.org/2008/11/barringtons-theorem.html>


---

### Answer by username_2 on 2010-08-19. Score: 14

$NL$ is closed under complementation.


---

### Answer by username_6 on 2010-08-21. Score: 12

I would say the recent work of Jain, Upadhyay and Watrous showing that QIP = IP = PSPACE is quite surprising. My opinion is that it isn't so much that QIP = IP is interesting but rather the fact that all of QIP can be simulated in a 3 round quantum interactive proof. A rather cool demonstration of the power of quantum parallelism.

Something that continues to surprise me is that BPP is likely to be P - It brings up a lot of philosophical questions regarding the nature of randomness.

> **Comments:**
> **username_7**: QIP = QIP(3) has been known for about 10 years now. The QIP = PSPACE paper did not show that.  
> **username_8**: The recent result QIP=PSPACE is by Jain, Ji, Upadhyay and Watrous.  

---

### Answer by username_9 on 2010-08-19. Score: 11

[Gödel's incompleteness theorems](http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems)


---

### Answer by username_2 on 2010-08-19. Score: 10

Razborov-Rudich Natural Proofs theorem.

(AFAIK) People were very hopeful about proving circuit lower bounds but after this theorem many stopped working and moved to other topics.


---

### Answer by username_10 on 2010-09-09. Score: 10

*The counting version of the Monotone-SAT problem is #P-complete.*

A Monotone-SAT instance is a propositional formula $F$ with the following restriction: every variable either always occurs positive or always occurs negative (in other words, every literal in $F$ is a pure literal).

I was very surprised by this result, because the decision version of the Monotone-SAT problem is trivial.

It's widely known that there exist decision problems in P whose counting versions are #P-complete (one example is 2-SAT). But this case is a bit "different" in my opinion: finding a satisfying assignment of a Monotone-SAT instance is not only easy (as, for example, finding a satisfying assignment of a 2-SAT instance), it's dramatically trivial. Not just easy: trivial, literally. Note that given, say, a 2-SAT instance, it can be either satisfiable or unsatisfiable of course; while given a Monotone-SAT instance you know in advance that it is certainly satisfiable: it cannot be unsatisfiable, no way: this confirms that, even both problems are easy, their levels of "decision-easiness" are different. On the other hand, their levels of "counting-uneasiness" is exactly the same.

This strong contrast between the following facts

1. Deciding Monotone-SAT is dumb-trivial
2. Counting Monotone-SAT is extremely-hard

is IMHO at least fascinating.


---

### Answer by username_9 on 2010-08-19. Score: 5

That the axioms of [Choice](http://en.wikipedia.org/wiki/Axiom_of_choice) and [Determinacy](http://en.wikipedia.org/wiki/Axiom_of_determinacy) are not compatible.


---

