<p>See the <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo" rel="nofollow">complexity zoo</a> and <a href="http://en.wikipedia.org/wiki/Complexity_class" rel="nofollow">wikipedia</a> and <a href="http://www.cs.umass.edu/~immerman/complexity_theory.html" rel="nofollow">Immermann</a>.</p>

CC BY-SA 2.5
2010-09-30T22:59:12.777Z
2010-09-30T23:04:29.650Z
2010-09-30T23:04:29.650Z
Dave Clarke
<p>I like <a href="http://rads.stackoverflow.com/amzn/click/0201530821" rel="nofollow">Papadimitriou's book</a>.</p>

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

<p>The relevant sections are:</p>

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

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

<p><strong>EDIT:</strong> I also recommend Complexity Zoo's <a href="http://www.math.ucdavis.edu/~greg/zoology/diagram.xml" rel="nofollow">Active Inclusion Diagram</a> (requires Firefox 1.5 or later, or Opera 9 or later). If you don't have that, you may try Zoo's <a href="http://www.math.ucdavis.edu/~greg/zoology/diagram.pdf" rel="nofollow">Static Inclusion Diagram</a>.</p>

CC BY-SA 2.5
2010-09-30T22:51:33.603Z
2010-09-30T23:24:30.910Z
2010-09-30T23:24:30.910Z
Sadeq Dousti
<p>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)</p>

<p>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?</p>

<p>Thank you.</p>

CC BY-SA 2.5
2010-09-30T22:53:20.400Z
To those who down-vote, or vote to close: Please see http://meta.cstheory.stackexchange.com/q/396/873
Sadeq Dousti
CC BY-SA 2.5
2010-09-30T23:03:48.737Z
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](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/229#229)).
Jukka Suomela
CC BY-SA 2.5
2010-09-30T23:05:01.880Z
Answer can be found by googling.
Dave Clarke
CC BY-SA 2.5
2010-09-30T23:07:56.623Z
@Jukka: You are right, yet I think we can help OP to restate the question. For example, one can ask: What are you exactly after? Do you have anything special in mind? Allowing some time will resolve such issues. As per the link on meta I just posted, please do not down-vote/vote-to-close quickly after a question is posted.
Sadeq Dousti
CC BY-SA 2.5
2010-09-30T23:13:26.973Z
The Zoo has a specific section called the Petting Zoo, which seems to be exactly what you are looking for.
András Salamon
CC BY-SA 2.5
2010-09-30T23:14:20.030Z
@Sadeq: Actually it seems that we already waited *too* long before closing this question. You already gave an answer and the answer was accepted.
Jukka Suomela
CC BY-SA 2.5
2010-09-30T23:20:11.093Z
@Jukka: I beg to differ. No offence, but if I were muad, I would accept an answer in a rush, before the question gets too attention, resulting in more negative reps. In fact, I have made such a decision when I posted one of my earliest questions :)
Sadeq Dousti
CC BY-SA 2.5
2010-09-30T23:54:36.590Z
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](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/361#361). 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.)
Jukka Suomela
CC BY-SA 2.5
2010-10-01T01:05:14.003Z
I lean toward closing only because any decent textbook on complexity theory would answer your question. And Complexity Zoo is the perfect place for checking separations/inclusions and references. As Jukka said, please don't be discouraged.
Kaveh
<complexity-classes>
Complexity Classes - separations and inclusions
muad
# Complexity Classes - separations and inclusions

(Asked by: username_0 on 2010-09-30)

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.

**Tags:** complexity-classes
> **Comments:**
> **username_1**: To those who down-vote, or vote to close: Please see http://meta.cstheory.stackexchange.com/q/396/873  
> **username_2**: 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](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/229#229)).  
> **username_3**: Answer can be found by googling.  
> **username_1**: @Jukka: You are right, yet I think we can help OP to restate the question. For example, one can ask: What are you exactly after? Do you have anything special in mind? Allowing some time will resolve such issues. As per the link on meta I just posted, please do not down-vote/vote-to-close quickly after a question is posted.  
> **username_4**: The Zoo has a specific section called the Petting Zoo, which seems to be exactly what you are looking for.  
> **username_2**: @Sadeq: Actually it seems that we already waited *too* long before closing this question. You already gave an answer and the answer was accepted.  
> **username_1**: @Jukka: I beg to differ. No offence, but if I were muad, I would accept an answer in a rush, before the question gets too attention, resulting in more negative reps. In fact, I have made such a decision when I posted one of my earliest questions :)  
> **username_2**: 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](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/361#361). 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.)  
> **username_5**: I lean toward closing only because any decent textbook on complexity theory would answer your question. And Complexity Zoo is the perfect place for checking separations/inclusions and references. As Jukka said, please don't be discouraged.  

---

## 2 answers

### Answer by username_1 on 2010-09-30. Score: 7 | Accepted answer

I like [Papadimitriou's book](http://rads.stackoverflow.com/amzn/click/0201530821).

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](http://www.math.ucdavis.edu/~greg/zoology/diagram.xml) (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](http://www.math.ucdavis.edu/~greg/zoology/diagram.pdf).


---

### Answer by username_3 on 2010-09-30. Score: 1

See the [complexity zoo](http://qwiki.stanford.edu/wiki/Complexity_Zoo) and [wikipedia](http://en.wikipedia.org/wiki/Complexity_class) and [Immermann](http://www.cs.umass.edu/~immerman/complexity_theory.html).


---

