3
$\begingroup$

What are the basic complexity class seperation and inclusion results that everybody should know? (I mean specifically results that are known, and the proofs can be understood by a non-expert)

It would be great to have a book or paper (or set of papers) which go through and prove all the simplest and most fundamental results in this area. Where could I find it?

Thank you.

Improve this question
$\endgroup$
9
  • $\begingroup$ To those who down-vote, or vote to close: Please see meta.cstheory.stackexchange.com/q/396/873 $\endgroup$
    – Sadeq Dousti
    Sep 30, 2010 at 22:53
  • 1
    $\begingroup$ I voted to close this as off-topic. The question seems to be too elementary (as we can see from the answers below: one is a very well-known textbook and the other one is a web site from our faq). $\endgroup$
    – Jukka Suomela
    Sep 30, 2010 at 23:03
  • 1
    $\begingroup$ Answer can be found by googling. $\endgroup$
    – Dave Clarke
    Sep 30, 2010 at 23:05
  • 3
    $\begingroup$ The Zoo has a specific section called the Petting Zoo, which seems to be exactly what you are looking for. $\endgroup$
    – András Salamon
    Sep 30, 2010 at 23:13
  • 1
    $\begingroup$ You got a useful answer to your question; hence you shouldn't be discouraged. (Even if this question was closed, and even if you hadn't had got useful answers by then, you shouldn't be discouraged. Closing is cheap, it doesn't cost your reputation, and you have always the opportunity to try to rephrase your question and re-ask it.) $\endgroup$
    – Jukka Suomela
    Sep 30, 2010 at 23:54

2 Answers 2

Reset to default
7
$\begingroup$

I like Papadimitriou's book.

Specially, it has "Class Review" sections at the end of several chapters, illustrating the relations among complexity classes.

The relevant sections are:

  • Section 10.4.1 (page 235): P, NP, coNP.
  • Section 11.5.1 (page 272): P, ZPP, RP, coRP, BPP, NP, coNP, PP.
  • Section 15.5.1 (page 385): AC, NC, RNC, P.
  • Section 16.4.1 (page 405): NC$_1$, L, SL, RL, SC, NL, PolyL, P.
  • Section 17.3.1 (page 433): PH and PSPACE.
  • Section 20.2.1 (page 499): P, NP, coNP, PSPACE, EXP, NEXP, coNEXP, EXPSPACE, 2-EXP, ELEMENTARY, R.

The book also includes a nice take on time- and space-hierarchy theorems; see Chapter 7.

EDIT: I also recommend Complexity Zoo's Active Inclusion Diagram (requires Firefox 1.5 or later, or Opera 9 or later). If you don't have that, you may try Zoo's Static Inclusion Diagram.

Improve this answer
$\endgroup$
1
$\begingroup$

See the complexity zoo and wikipedia and Immermann.

Improve this answer
$\endgroup$

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