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.

$\endgroup$

closed as not a real question by Jukka Suomela, Dave Clarke, Tsuyoshi Ito, Aaron Roth, Kaveh Oct 1 '10 at 0:57

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ To those who down-vote, or vote to close: Please see meta.cstheory.stackexchange.com/q/396/873 $\endgroup$ – M.S. Dousti Sep 30 '10 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 '10 at 23:03
  • 1
    $\begingroup$ Answer can be found by googling. $\endgroup$ – Dave Clarke Sep 30 '10 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 '10 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 '10 at 23:54
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.

$\endgroup$
1
$\begingroup$

See the complexity zoo and wikipedia and Immermann.

$\endgroup$

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