Si un ordinador no pot utilitzar un algoritme per resoldre un conjunt de problemes, llavors aquests es consideren temps polinòmic no determinista a diferència de quina categoria de complexitat? Tenint en compte la pregunta anterior, escriu un context que conté la resposta. Pot ser de 1 a 20 frases. Context:
La classe de complexitat P és sovint vista com una abstracció matemàtica que modela les tasques computacionals que admeten un algoritme eficient. Aquesta hipòtesi s'anomena tesi Cobham-Edmonds. La classe de complexitat NP, d'altra banda, conté molts problemes que la gent voldria resoldre de manera eficient, però per als quals no es coneix cap algoritme eficient, com el problema de satisfiabilitat booleana, el problema de camí hamiltonià i el problema de cobertura de vèrtexs. Atès que les màquines de Turing deterministes són màquines de Turing especials no deterministes, es pot observar fàcilment que cada problema en P també és membre de la classe NP.