Una curiosità su classi P,NP e NPC

[lordb]

Ciao a tutti,
mi è chiaro perchè si abbia: $NP text{ completi}sub NP$, $P sub NP$ e forse $Pnntext{NP completi}={}$.

Tuttavia non mi è chiaro il perchè non possa esistere una classe di equivalenza formata dai problemi che possano essere verificati solo in un tempo esponenziale da una macchina sequenziale deterministica o meno.

Grazie in anticipo

[lordb]

UP

[lordb]

Up

[Rggb1]

"lordb":Tuttavia non mi è chiaro il perchè non possa esistere una classe di equivalenza formata dai problemi che possano essere verificati solo in un tempo esponenziale...

A me invece non è chiara la domanda.

Usiamo questo
http://en.wikipedia.org/wiki/Computatio ... ty_classes
come riferimento, e poi ne riparliamo.

[lordb]

Ok, grazie per la risposta.

In questi giorni vedrò di leggermi la pagina da te linkata e, se necessario, di riformulare meglio la domanda.