Ciao,
dunque sappiamo che:
- P incluso in NP;
- NP-C incluso in NP;
- NP incluso in problemi a soluzione esponenziale;
- esponenziali incluso in problemi decidibili;
Ora, possiamo dire:
- esponenziali - P (in pratica la "ciambella" che ha come buco P) = problemi intrattabili;
- decidibili - intrattabili = trattabili;
???????
In pratica se fosse vero quello che penso io, vuol dire che ci sono problemi trattabili che ammettono solo soluzioni NON esponenziali e che ci sono problemi con soluzioni esponenziali e senza soluzioni polinomiali ma NON NP (forse sono gli NP-hard?).
Inoltre, secondo le 4 ipotesi poste all'inizio, P sarebbe un caso particolare di problemi NP (ovvero l'insieme degli NP risolvibili anche con algoritmi polinomiali). Perché?
Potete chiarirmi un po' le idee a riguardo?