37
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ I realize that this may be out-of-scope, but it's good to check the boundaries in beta, right? :) $\endgroup$
    – Lev Reyzin ♦
    Commented Aug 18, 2010 at 18:14
  • 2
    $\begingroup$ Certainly on-topic, I would say. $\endgroup$
    – Jukka Suomela
    Commented Aug 18, 2010 at 19:16

9 Answers 9

Reset to default
29
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ wow I somehow missed this! Probably no need for us to make a list then :) $\endgroup$
    – Lev Reyzin ♦
    Commented Aug 18, 2010 at 18:21
  • 2
    $\begingroup$ Perhaps it would be good to focus on surprising results since 2005 here. $\endgroup$
    – Jukka Suomela
    Commented Aug 18, 2010 at 19:20
21
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ This was very supervising for me because I had heard many times that diagonalization cannot seprate $NP$ from $P$. $\endgroup$
    – Kaveh
    Commented Aug 19, 2010 at 21:37
  • 1
    $\begingroup$ 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... $\endgroup$
    – Joshua Grochow
    Commented Aug 22, 2010 at 17:00
  • 3
    $\begingroup$ D. Kozen, "Indexing of subrecursive classes", 1978 $\endgroup$
    – Kaveh
    Commented Aug 22, 2010 at 17:55
  • $\begingroup$ how does this relate to the Baker Gill Solovay 1975 result? $\endgroup$
    – vzn
    Commented Jul 16, 2012 at 20:28
19
$\begingroup$

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

Improve this answer
$\endgroup$
14
$\begingroup$

$NL$ is closed under complementation.

Improve this answer
$\endgroup$
12
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ QIP = QIP(3) has been known for about 10 years now. The QIP = PSPACE paper did not show that. $\endgroup$
    – Robin Kothari
    Commented Sep 11, 2010 at 2:30
  • $\begingroup$ The recent result QIP=PSPACE is by Jain, Ji, Upadhyay and Watrous. $\endgroup$
    – Tsuyoshi Ito
    Commented Dec 8, 2010 at 23:41
11
$\begingroup$

Gödel's incompleteness theorems

Improve this answer
$\endgroup$
10
$\begingroup$

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.

Improve this answer
$\endgroup$
10
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

That the axioms of Choice and Determinacy are not compatible.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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