Classe di complessità: differenze tra le versioni

Versione delle 03:30, 25 lug 2009

Versione delle 17:33, 6 nov 2009

Riga 10:

==Relazioni tra classi di complessità==

La seguente tabella mostra alcune classi di problemi (o di 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"

Riga 74:

|

{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"

| align="center" | [[GrammaticaLinguaggio sensibiledipendente aldal contesto|Tipo 1 (sensibile al contesto)]]

|}

| [[Immagine:solidLine.png]]

Riga 170:

| colspan=3 |

{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"

| align="center" | [[GrammaticaLinguaggio liberalibero dal contesto|Tipo 2 (libera dal contesto)]]

|}

|- align="center"

Riga 177:

| colspan=3 |

{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"

| align="center" | [[GrammaticaLinguaggio regolare|Tipo 3 (Regolare)]]

|}

|}