16
$\begingroup$

A few years ago Lance Fortnow listed his favorite theorems in complexity theory: (1965-1974) (1975-1984) (1985-1994) (1995-2004) But he restricted himself (check the third one) and his last post is now 6 years old. An updated and more comprehensive list can be helpful.

What are the most important results (and papers) in complexity theory that every one should know? What are your favorites?

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ The list of important results in complexity theory that every complexity theorist "should" know is enormous. I think a better question would be: "what are the most important results in complexity theory that every mathematician should know?" $\endgroup$
    – Ryan Williams
    Commented Aug 4, 2010 at 14:14
  • 1
    $\begingroup$ How do you expect answers to this question to be different from what Lance did? Do you want also things not on his lists? Do you want extra 'votes' for things already mentioned by him? (I find his lists pretty comprehensive: his favorites ~ results complexity theorists should know) $\endgroup$
    – Mitch
    Commented Aug 4, 2010 at 14:22
  • $\begingroup$ @Ryan: That is also a nice question. (Maybe we should start a community wiki for it for that also?) But I was more thinking about having a list of things that a first year graduate student who is going to work in complexity theory should learn (or know). $\endgroup$
    – Kaveh
    Commented Aug 4, 2010 at 16:33
  • $\begingroup$ @Mitch: Repeating the results from Lance is OK, but I would like to have other perspective and results not mentioned by him, i.e. a more comprehensive list. His lists does not have anything from last 6 years. $\endgroup$
    – Kaveh
    Commented Aug 4, 2010 at 16:33

5 Answers 5

Reset to default
7
$\begingroup$

I think Lance's choices from the past are pretty comprehensive, although I might add a couple more from the lower bounds department which for some reason are not well-known:

John E. Hopcroft, Wolfgang J. Paul, Leslie G. Valiant: On Time Versus Space. J. ACM 24(2): 332-337 (1977)

Wolfgang J. Paul, Nicholas Pippenger, Endre Szemerédi, William T. Trotter: On Determinism versus Non-Determinism and Related Problems (Preliminary Version) FOCS 1983: 429-438

The first paper shows that $TIME[t] \subseteq SPACE[t/\log t]$ (so, $SPACE[t]$ is not contained in $TIME[o(t \log t)]$). This result has since been generalized (from Turing machines) to all the "modern" models of computation. (For references, look at citations on Google scholar.)

The second paper shows that for multitape Turing machines, $NTIME[n] \neq TIME[n]$. This is really the only generic separation of nondeterministic and deterministic time that we know. It is not known whether this result extends to more modern models of computation. Perhaps one reason why these results are not better known is that many seem to believe that their approaches are a dead end, more or less. (There's some mathematical evidence for that: the techniques do break down if you try to push them any further, but it's always possible these techniques could be combined with something new.)

As for the last 6 years... I'll have to think about my choices for the "best papers" since then. Expect an update to this answer later. I think the following work over the last six years should be among those that everyone should know about. That doesn't mean that I think they're "best", it just means I am trying to answer the original question. It's a very biased list.

  • Irit Dinur's combinatorial proof of the PCP theorem

  • Omer Reingold's logspace algorithm for st-connectivity

  • Ketan Mulmuley's geometric complexity theory program

  • Subhash Khot's Unique Games Conjecture and what it entails (this was initiated earlier than 6 years ago but it has become much more important in the last 6 years)

  • Russell Impagliazzo and Valentine Kabanets' "Derandomizing polynomial identity testing means proving circuit lower bounds"

  • Lance Fortnow et al.'s time-space lower bounds for SAT (this is excluding all work that I have personally done on this, you can decide for yourself if you should know about that)

I left out a bunch of very important things because the list is 6 items. Sorry.

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

There's the Bazzi/Razborov/Braverman sequence on fooling AC0 circuits.

Improve this answer
$\endgroup$
4
$\begingroup$

My favourite results are (1) the existence of NP-complete problems (Cook), (2) the Baker-Gil-Solovay theorem that whether P=NP holds relativized to on oracle depends on the oracle, and (3) Fagin's characterization of NP in terms of second order logic.

I am not so much interested in the large number of proofs that show that a certain problem is NP-complete, but the fact that there is some problem that is NP-complete is remarkable and important. And Cook's SAT is actually natural. (2) shows that several approaches will not work when one wants to settle P versus NP. (3) gives a much more natural definition of the class NP. Fagin's formulation (NP is the class of graph properties (of finite graphs) that can be expressed with a formula that has an n-ary second order existential quantifier in front, followed by a first order formula) indicates that NP vs co-NP is a very fundamental question as well (can second order existential quantification be replaced by second order universal quantification?).

Improve this answer
$\endgroup$
1
  • $\begingroup$ The mere fact that NP-complete problems exist is (or should be) obvious and immediate once one has the insight to consider the concept in the first place: the problem "Given a nondeterministic machine P, and a number N in unary, determine if it is possible for P to halt in N steps" is clearly NP-complete. The fact that so many other naturally arising problems turn out to be NP-complete is what makes it interesting. $\endgroup$
    – Sridhar Ramesh
    Commented Aug 9, 2010 at 20:37
4
$\begingroup$

I think you should add as a recent result the proof for QIP=IP=PSPACE

Improve this answer
$\endgroup$
5
  • $\begingroup$ Is there a particular reason you chose this result? $\endgroup$
    – András Salamon
    Commented Aug 5, 2010 at 17:49
  • $\begingroup$ Well, I have a bias here to be honest but I propose this as a result for the 2005-2010 period. First, to my knowledge, this is the best relation we have between classical and quantum classes. There are other good results on upper bounds for BQP, but this is the only result where a quantum complexity class is completely characterized. Second, although I don't know the complete details, the proof seems to be non-relativizing. And that's important because we can try to learn from here and use it to proof other non-relativizing results. Although, other people already tried that. $\endgroup$
    – Marcos Villagra
    Commented Aug 5, 2010 at 23:29
  • 1
    $\begingroup$ Two corrections: first, there were several previous results that completely characterized a quantum complexity class in terms of a classical class (for example, QRG=EXP, NQP=coC_{=}P, PostBQP=PP, and BQP_CTC=PSPACE). Second, while PSPACE in QIP is nonrelativizing, the "new" direction (QIP in PSPACE) is relativizing. $\endgroup$
    – Scott Aaronson
    Commented Aug 6, 2010 at 1:31
  • $\begingroup$ Thanks for the info. But what I wanted to point out is that for the "lower" classical complexity classes (PSPACE and below) this is the best, is that correct? Although the NQP=coC_{=}P result seems to be at a really low level. $\endgroup$
    – Marcos Villagra
    Commented Aug 6, 2010 at 2:22
  • $\begingroup$ Also BQPSPACE=PSPACE. $\endgroup$
    – Robin Kothari
    Commented Aug 7, 2010 at 14:27
3
$\begingroup$

Well I guess after Cook, Karp's paper "Reducibility among combinatorial problems" is the second most obligatory and canonical thing to mention. This paper was the first to demonstrate to the world the diversity and ubiquity of NP-complete problems.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .