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.

  • I realize that this may be out-of-scope, but it's good to check the boundaries in beta, right? :) – Lev Reyzin Aug 18 '10 at 18:14
  • 2
    Certainly on-topic, I would say. – Jukka Suomela Aug 18 '10 at 19:16
up vote 27 down vote accepted

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

  • wow I somehow missed this! Probably no need for us to make a list then :) – Lev Reyzin Aug 18 '10 at 18:21
  • 2
    Perhaps it would be good to focus on surprising results since 2005 here. – Jukka Suomela Aug 18 '10 at 19:20

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.

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

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

$NL$ is closed under complementation.

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.

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

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.

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.

That the axioms of Choice and Determinacy are not compatible.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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