|
==Relazioni tra classi di complessità==
La seguente tabella mostra alcune classi di problemi (o linguaggi, o grammatiche) che sono considerate nella teoria della complessità. Se la classe '''X''' è un [[sottoinsieme]] stretto di '''Y''', allora '''X''' è rappresentata sotto ad '''Y''', con una linea continua che li connette. Se '''X''' è un sottoinsieme, ma non si sa se '''X''' e '''Y''' sono insiemi uguali, allora la linea è tratteggiata. Tecnicamente, la suddivisione tra problemi solubili e insolubili appartiene più alla [[teoria della calcolabilità]], ma aiuta a vedere in prospettiva le classi di complessità.
{| cellpadding="0" cellspacing="0" border="0" align="center"
<table cellpadding="0" cellspacing="0" border="0"|- align="center">
| colspan=2 |
<tr align="center">
<td| colspan=2></td>4 |
<td colspan=4><table{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td
| align="center"> | [[Problemi di decisione]]</td></tr></table></td>
|}
</tr>
<tr|- align="center">
<td| colspan=2></td> |
<td>| [[Immagine:solidLine.png]]</td>
<td| colspan=2></td> |
<td>| [[Immagine:solidLine.png]]</td>
|- align="center"
</tr>
| colspan=3 |
<tr align="center">
<td colspan=3><table{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td
| align="center"> | [[Linguaggio ricorsivamente enumerabile|Tipo 0 (Ricorsivamente enumerabili)]]</td></tr></table></td>
|}
<td></td>
|
<td colspan=4><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">[[Problemi di decisione|Indecidibili]]</td></tr></table></td>
| colspan=4 |
</tr>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
<tr align="center">
| align="center" | [[Problemi di decisione|Indecidibili]]
<td colspan=3>[[Immagine:solidLine.png]]</td>
|}
</tr>
<tr|- align="center">
| colspan=3 | [[Immagine:solidLine.png]]
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">[[Linguaggio ricorsivo|Decidibile]]</td></tr></table></td>
|- align="center"
</tr>
| colspan=3 |
<tr align="center">
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
<td colspan=3>[[Immagine:solidLine.png]]</td>
| align="center" | [[Linguaggio ricorsivo|Decidibile]]
</tr>
|}
<tr align="center">
|- align="center"
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[EXPSPACE]]</td></tr></table></td>
| colspan=3 | [[Immagine:solidLine.png]]
</tr>
<tr|- align="center">
<td| colspan=3>[[Immagine:dottedLine.png]]</td> |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
</tr>
<tr| align="center"> | [[EXPSPACE]]
|}
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[EXPTIME]]</td></tr></table></td>
|- align="center"
</tr>
| colspan=3 | [[Immagine:dottedLine.png]]
<tr align="center">
|- align="center"
<td colspan=3>[[Immagine:dottedLine.png]]</td>
| colspan=3 |
</tr>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
<tr align="center">
| align="center" | [[EXPTIME]]
<td colspan=8><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[PSPACE]]</td></tr></table></td>
|}
</tr>
<tr|- align="center">
<td>| colspan=3 | [[Immagine:solidLinedottedLine.png]]</td>
|- align="center"
<td width=40>[[Immagine:solidLine.png]]</td>
| colspan=8 |
<td>[[Immagine:dottedLine.png]]</td>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
<td>[[Immagine:dottedLine.png]]</td>
| align="center" | [[PSPACE]]
<td></td>
|}
<td>[[Immagine:dottedLine.png]]</td>
|- align="center"
<td></td>
<td>| [[Immagine:dottedLinesolidLine.png]]</td>
| width=40 | [[Immagine:solidLine.png]]
</tr>
| [[Immagine:dottedLine.png]]
<tr align="center">
| [[Immagine:dottedLine.png]]
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">[[Grammatica sensibile al contesto|Tipo 1 (sensibile al contesto)]]</td></tr></table></td>
|
<td>[[Immagine:solidLine.png]]</td>
<td>| [[Immagine:dottedLine.png]]</td>
|
<td border="1">[[Immagine:dottedLine.png]]</td>
| [[Immagine:dottedLine.png]]
<td></td>
|- align="center"
<td>[[Immagine:dottedLine.png]]</td>
|
<td></td>
<td colspan=1><table{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreenlightBlue" width="100%" height="100%"><tr><td align="center">[[PSPACE-Completo|PSPACE-Completi]]</td></tr></table></td>
| align="center" | [[Grammatica sensibile al contesto|Tipo 1 (sensibile al contesto)]]
</tr>
|}
<tr align="center">
<td>| [[Immagine:solidLine.png]]</td>
<td>| [[Immagine:solidLinedottedLine.png]]</td>
<td>| border="1" | [[Immagine:dottedLine.png]]</td>
|
<td>[[Immagine:dottedLine.png]]</td>
| [[Immagine:dottedLine.png]]
<td></td>
|
<td>[[Immagine:dottedLine.png]]</td>
| colspan=1 |
</tr>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
<tr align="center">
| align="center" | [[PSPACE-Completo|PSPACE-Completi]]
<td>[[Immagine:solidLine.png]]</td>
|}
<td>[[Immagine:solidLine.png]]</td>
|- align="center"
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[Co-NP]]</td></tr></table></td>
<td>| [[Immagine:dottedLinesolidLine.png]]</td>
| [[Immagine:solidLine.png]]
<td></td>
| [[Immagine:dottedLine.png]]
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[NP (complessità)|NP]]</td></tr></table></td>
| [[Immagine:dottedLine.png]]
</tr>
|
<tr align="center">
<td>| [[Immagine:solidLinedottedLine.png]]</td>
|- align="center"
<td>[[Immagine:solidLine.png]]</td>
<td>| [[Immagine:dottedLinesolidLine.png]]</td>
<td>| [[Immagine:dottedLinesolidLine.png]]</td>
|
<td></td>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
<td>[[Immagine:dottedLine.png]]</td>
| align="center" | [[Co-NP]]
<td></td>
|}
<td>[[Immagine:dottedLine.png]]</td>
| [[Immagine:dottedLine.png]]
</tr>
|
<tr align="center">
| colspan=3 |
<td>[[Immagine:solidLine.png]]</td>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
<td>[[Immagine:solidLine.png]]</td>
| align="center" | [[NP (complessità)|NP]]
<td>[[Immagine:dottedLine.png]]</td>
|}
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[BPP (complessità)|BPP]]</td></tr></table></td>
|- align="center"
<td width=10></td>
| [[Immagine:solidLine.png]]
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[BQP]]</td></tr></table></td>
| [[Immagine:solidLine.png]]
<td width=10></td>
| [[Immagine:dottedLine.png]]
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[NP-Completo|NP-Completi]]</td></tr></table></td>
| [[Immagine:dottedLine.png]]
</tr>
|
<tr align="center">
<td>| [[Immagine:solidLinedottedLine.png]]</td>
|
<td>[[Immagine:solidLine.png]]</td>
<td>| [[Immagine:dottedLine.png]]</td>
|- align="center"
<td>[[Immagine:dottedLine.png]]</td>
| [[Immagine:solidLine.png]]
<td></td>
<td>| [[Immagine:dottedLinesolidLine.png]]</td>
| [[Immagine:dottedLine.png]]
</tr>
|
<tr align="center">
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
<td>[[Immagine:solidLine.png]]</td>
| align="center" | [[BPP (complessità)|BPP]]
<td>[[Immagine:solidLine.png]]</td>
|}
<td colspan=6><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[P (complessità)|P]]</td></tr></table></td>
| width=10 |
</tr>
|
<tr align="center">
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
<td>[[Immagine:solidLine.png]]</td>
| align="center" | [[BQP]]
<td>[[Immagine:solidLine.png]]</td>
|}
<td>[[Immagine:dottedLine.png]]</td>
| width=10 |
<td colspan=4></td>
|
<td>[[Immagine:dottedLine.png]]</td>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
</tr>
<tr| align="center"> | [[NP-Completo|NP-Completi]]
|}
<td>[[Immagine:solidLine.png]]</td>
|- align="center"
<td colspan=2><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[NC (complessità)|NC]]</td></tr></table></td>
| [[Immagine:solidLine.png]]
<td colspan=4></td>
| [[Immagine:solidLine.png]]
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[P-Completo|P-Completi]]</td></tr></table></td>
| [[Immagine:dottedLine.png]]
</tr>
| [[Immagine:dottedLine.png]]
<tr align="center">
|
<td>[[Immagine:solidLine.png]]</td>
<td| colspan=2>[[Immagine:solidLinedottedLine.png]]</td>
|- align="center"
</tr>
| [[Immagine:solidLine.png]]
<tr align="center">
| [[Immagine:solidLine.png]]
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">[[Grammatica libera dal contesto|Tipo 2 (libera dal contesto)]]</td></tr></table></td>
| colspan=6 |
</tr>
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
<tr align="center">
| align="center" | [[P (complessità)|P]]
<td colspan=3>[[Immagine:solidLine.png]]</td>
|}
</tr>
<tr|- align="center">
| [[Immagine:solidLine.png]]
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">[[Grammatica regolare|Tipo 3 (Regolare)]]</td></tr></table></td>
| [[Immagine:solidLine.png]]
</tr>
| [[Immagine:dottedLine.png]]
</table>
| colspan=4 |
| [[Immagine:dottedLine.png]]
|- align="center"
| [[Immagine:solidLine.png]]
| colspan=2 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
| align="center" | [[NC (complessità)|NC]]
|}
| colspan=4 |
|
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"
| align="center" | [[P-Completo|P-Completi]]
|}
|- align="center"
| [[Immagine:solidLine.png]]
| colspan=2 | [[Immagine:solidLine.png]]
|- align="center"
| colspan=3 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
| align="center" | [[Grammatica libera dal contesto|Tipo 2 (libera dal contesto)]]
|}
|- align="center"
| colspan=3 | [[Immagine:solidLine.png]]
|- align="center"
| colspan=3 |
{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"
| align="center" | [[Grammatica regolare|Tipo 3 (Regolare)]]
|}
|}
==Voci correlate==
| 