Newsgroup: it.scienza.informatica
Titolo: Tempo polinomiale: deterministico o non deterministico?

salve a tutti, sto studiando per un corso di informatica teorica e non
mi è
chiara la sfumatura tra
tempo polinomiale determ. e non determ....
Nel senso: da quello che ho capito eseguire una macchina di Turing non
deterministaica equivale a eseguirne "tante" deterministiche... e in
questo
modo "sembra" che il tempo utile per eseguire un algoritmo sia
polinomiale...
ma non è solo un paliativo??
in realtà un tempo polinomiale non det non è PER FORZA MAGGIORE di
uno
polinom. determ??? (considerando ovviamente n grandi (non mi interessa
sui
casi piccoli))
Insomma qual'è l'interesse ad ottenre un tempo polinomiale non
deterministico, se poi in REALTA' e un tempo PIU che polinomiale
normale
(cioe determ.)
(scusate i discorsi un po intricati)
Grazie


In realta` il problema fondamentale e` che c'e` tutta una classe di 
problemi di cui non si conosce la complessita` vera: nessuno oggigiorno 
sa dire se si riescono a risolvere in tempo polinomiale (per dimostrare 
questo bisognerebbe trovare un algoritmo polinomiale per risolvere 
questi problemi, o almeno dimostrare che questo algoritmo esiste), 
oppure se tale algoritmo non puo` esistere (e quindi bisognerebbe 
dimostrare che tutti i possibili algoritmi che risolvono il problema 
hanno una complessita` non polinomiale).
Sono pero` problemi reali, per cui sarebbe utile avere uno straccio di 
idea su "quanto" sono difficili, se un problema e` "piu` o meno 
difficile" di un altro, ecc.
Allora, per avere un'idea un po' meno vaga, aspettando che qualcuno 
faccia una delle due dimostrazioni, gli scienziati si sono inventati una 
"macchina fasulla", che non esiste in realta`. Dicono: facciamo finta di 
avere una macchina di Turing non deterministica: qual e` la complessita` 
del problema XXX su questa macchina? Se si dimostra che su quella 
macchina il problema e` polinomiale, allora il problema appartiene alla 
classe NP. In questo modo sto dicendo una specie di "upper bound" sulla 
complessita` del problema: non so bene qual e` la complessita` vera del 
problema, ma almeno ne ho un'idea sommaria. Se un domani qualcuno trova 
un modo polinomiale di implementare l'oracolo della macchina di Turing 
non deterministica, allora avro` dimostrato che la complessita` di quel 
problema e` polinomiale.
Nell'attesa, quel problema resta nel "limbo" NP.
Ciao,
Marco


OTTIMO grazie della tua risposta...
vorrei aggiungere una domanda però:
stando le cose al giorno di oggi, dove la MDT non-det può essere simulata 
con una MDT determ (almeno la dimostraz che conosco) a 3 nastri (che tanto 
per un teorema si potrebbe ridurre cmq ad un solo nastro) cosa accade sui 
tempi?
Ovvero dato un problema NP, che risolvo in modo polinom non-determ con una 
MDT non-det., visto che posso sempre operare la conversione in MDT determ, 
allora in termini deterministici che complessità ho??
grazie ancora 

 allora in termini deterministici che complessità ho??
A rigore dovrei dire "non si sa". Per ora i metodi che conosciamo per 
simulare la nondeterministica hanno complessita` esponenziale (quindi la 
macchina deterministica, emulando la nondeterministica, esegue un numero 
esponenziale di passi).
Se uno trova un metodo polinomiale avra` dimostrato P=NP.
Ciao,
Marco