Teoria della complessità computazionale: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
→Classi di complessità: Corretto errore di battitura Etichette: Modifica da mobile Modifica da applicazione mobile Modifica da applicazione Android |
→Classi di complessità: correzione con italiano lievemente più tecnico Etichette: Modifica da mobile Modifica da applicazione mobile Modifica da applicazione Android |
||
Riga 58:
Altre relazioni non sono note.
L'implicazione pratica principale data da questa classificazione è la suddivisione in problemi che sappiamo risolvere in modo efficiente e in problemi che non sappiamo se possono essere risolti in modo efficiente. Infatti, calcolare il ''caso ottimo'' di un algoritmo di solito non è un'operazione troppo complicata
Data questa premessa, osserviamo che se sappiamo che un certo problema <math>\Pi \in \mbox{NP}</math>, è in generale un errore dire <math>\Pi \notin \mbox{P}</math> perché non è possibile dirlo, data anche l'inclusione ''non stretta'' di <math>P</math> in <math>\mbox{NP}</math>. Infatti, pur sapendo che <math>\mbox{P} \subseteq \mbox{NP}</math>, non si sa se <math>\mbox{P} \subset \mbox{NP}</math> o se <math>\mbox{P} = \mbox{NP} </math>, e questo è uno dei grandi problemi ancora aperti nell'informatica teorica, tanto da meritarsi un posto nei [[problemi per il millennio]].
| |||