Un algoritmo che può esibire comportamenti diversi in più esecuzioni anche quando si utilizza lo stesso input è indicato come? Dato il contesto della domanda precedente, scrivi il contesto che contiene la risposta. Può essere da 1 a 20 frasi. Contesto:
La classe di complessità P è spesso vista come un'astrazione matematica che modella quei compiti computazionali che ammettono un algoritmo efficiente. Questa ipotesi è chiamata tesi di Cobham-Edmonds. La classe di complessità NP, d'altra parte, contiene molti problemi che le persone vorrebbero risolvere in modo efficiente, ma per i quali non è noto alcun algoritmo efficiente, come il problema di soddisfacibilità booleana, il problema del percorso hamiltoniano e il problema della copertura dei vertici. Poiché le macchine di Turing deterministiche sono speciali macchine di Turing non deterministiche, si osserva facilmente che ogni problema in P è anche membro della classe NP.