Editing Complexity class (section)

==Summary of relationships between complexity classes==
The following table shows some of the classes of problems that are considered in complexity theory.  If class '''X''' is a strict [[subset]] of '''Y''', then '''X''' is shown below '''Y''' with a dark line connecting them.  If '''X''' is a subset, but it is unknown whether they are equal sets, then the line is lighter and dotted. Technically, the breakdown into decidable and undecidable pertains more to the study of [[computability theory]], but is useful for putting the complexity classes in perspective.
{| cellpadding="0" cellspacing="0" border="0" style="margin:auto;"
|- style="text-align:center;"
| colspan=2 |

| colspan=4 |
{| cellpadding="0" cellspacing="0" border="1" style="background:lightBlue; width:100%; height:100%;"
|-
| style="text-align:center;" | [[decision problem|Decision Problem]]
|}
|- style="text-align:center;"
| colspan=2 |
| [[File:solidLine.png]]
| colspan=2 |
| [[File:solidLine.png]]
|- style="text-align:center;"
| colspan=3 |
{| cellpadding="0" cellspacing="0" border="1" style="background:lightBlue; width:100%; height:100%;"
|-
| style="text-align:center;" | [[recursively enumerable language|Type 0 (Recursively enumerable)]]
|}
|
| colspan=4 |
{| cellpadding="0" cellspacing="0" border="1" style="background:lightBlue; width:100%; height:100%;"
|-
| style="text-align:center;" | [[List of undecidable problems|Undecidable]]
|}
|- style="text-align:center;"
| colspan=3 | [[File:solidLine.png]]
|- style="text-align:center;"
| colspan=3 |
{| cellpadding="0" cellspacing="0" border="1" style="background:lightBlue; width:100%; height:100%;"
|-
| style="text-align:center;" | [[recursive language|Decidable]]
|}
|- style="text-align:center;"
| colspan=3 | [[File:solidLine.png]]
|- style="text-align:center;"
| colspan=3 |
{| cellpadding="0" cellspacing="0" border="1" style="background:lightGreen; width:100%; height:100%;"
|-
| style="text-align:center;" | [[EXPSPACE]]
|}
|- style="text-align:center;"
| colspan=3 | [[File:dottedLine.png]]
|- style="text-align:center;"
| colspan=3 |
{| cellpadding="0" cellspacing="0" border="1" style="background:lightGreen; width:100%; height:100%;"
|-
| style="text-align:center;" | [[NEXPTIME]]
|}
|- style="text-align:center;"
| colspan=3 | [[File:dottedLine.png]]
|- style="text-align:center;"
| colspan=3 |
{| cellpadding="0" cellspacing="0" border="1" style="background:lightGreen; width:100%; height:100%;"
|-
| style="text-align:center;" | [[EXPTIME]]
|}
|- style="text-align:center;"
| colspan=3 | [[File:dottedLine.png]]
|- style="text-align:center;"
| colspan=8 |
{| cellpadding="0" cellspacing="0" border="1" style="background:lightGreen; width:100%; height:100%;"
|-
| style="text-align:center;" | [[PSPACE]]
|}
|- style="text-align:center;"
| [[File:solidLine.png]]
| width=40 | [[File:solidLine.png]]
| [[File:dottedLine.png]]
| [[File:dottedLine.png]]
|
| [[File:dottedLine.png]]
|- style="text-align:center;"
|
{| cellpadding="0" cellspacing="0" border="1" style="background:lightBlue; width:100%; height:100%;"
|-
| style="text-align:center;" | [[context-sensitive grammar|Type 1 (Context Sensitive)]]
|}
| [[File:solidLine.png]]
| [[File:dottedLine.png]]
| border="1" | [[File:dottedLine.png]]
|
| [[File:dottedLine.png]]
|- style="text-align:center;"
| [[File:solidLine.png]]
| [[File:solidLine.png]]
| [[File:dottedLine.png]]
| [[File:dottedLine.png]]
|
| [[File:dottedLine.png]]
|- style="text-align:center;"
| [[File:solidLine.png]]
| [[File:solidLine.png]]
|
{| cellpadding="0" cellspacing="0" border="1" style="background:lightGreen; width:100%; height:100%;"
|-
| style="text-align:center;" | [[co-NP]]
|}
|
{| cellpadding="0" cellspacing="0" border="1" style="background:lightGreen; width:100%; height:100%;"
|-
| style="text-align:center;" | [[BQP]]
|}
|
| colspan=2 |
{| cellpadding="0" cellspacing="0" border="1" style="background:lightGreen; width:100%; height:100%;"
|-
| style="text-align:center;" | [[NP (complexity)|NP]]
|}
|- style="text-align:center;"
| [[File:solidLine.png]]
| [[File:solidLine.png]]
| [[File:dottedLine.png]]
| [[File:dottedLine.png]]
|
| [[File:dottedLine.png]]
|- style="text-align:center;"
| [[File:solidLine.png]]
| [[File:solidLine.png]]
| [[File:dottedLine.png]]
|
{| cellpadding="0" cellspacing="0" border="1" style="background:lightGreen; width:100%; height:100%;"
|-
| style="text-align:center;" | [[Bounded-error probabilistic polynomial|BPP]]
|}
| width=10 |
| [[File:dottedLine.png]]
|- style="text-align:center;"
| [[File:solidLine.png]]
| [[File:solidLine.png]]
| [[File:dottedLine.png]]
| [[File:dottedLine.png]]
|
| [[File:dottedLine.png]]
|- style="text-align:center;"
| [[File:solidLine.png]]
| [[File:solidLine.png]]
| colspan=5 |
{| cellpadding="0" cellspacing="0" border="1" style="background:lightGreen; width:100%; height:100%;"
|-
| style="text-align:center;" | [[P (complexity)|P]]
|}
|- style="text-align:center;"
| [[File:solidLine.png]]
| [[File:solidLine.png]]
| [[File:dottedLine.png]]
|- style="text-align:center;"
| [[File:solidLine.png]]
| colspan=2 |
{| cellpadding="0" cellspacing="0" border="1" style="background:lightGreen; width:100%; height:100%;"
|-
| style="text-align:center;" | [[NC (complexity)|NC]]
|}
|- style="text-align:center;"
| [[File:solidLine.png]]
| colspan=2 | [[File:solidLine.png]]
|- style="text-align:center;"
| colspan=3 |
{| cellpadding="0" cellspacing="0" border="1" style="background:lightBlue; width:100%; height:100%;"
|-
| style="text-align:center;" | [[context-free grammar|Type 2 (Context Free)]]
|}
|- style="text-align:center;"
| colspan=3 | [[File:solidLine.png]]
|- style="text-align:center;"
| colspan=3 |
{| cellpadding="0" cellspacing="0" border="1" style="background:lightBlue; width:100%; height:100%;"
|-
| style="text-align:center;" | [[regular grammar|Type 3 (Regular)]]
|}
|}