Surprising Results in Complexity (Not on the Complexity Blog List)

Question

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 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.

Answer 1

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

Answer 2

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.

Answer 3

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 4

$NL$ is closed under complementation.

Answer 5

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.

Answer 6

Gödel's incompleteness theorems

Answer 7

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 8

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 9

That the axioms of Choice and Determinacy are not compatible.