Continua il dibattito su problemi P e NP (come dicevo, una questione fondamentale). Un altro problema NP, il 3-sat, viene ridotto a P. Ma, come avviene per il problema del commesso viaggiatore, qualcuno non è d’accordo. Al solito: fatemi sapere chi ha ragione, che non ci capisco molto. Ma dicono sia importante.
2 Commenti
vabbe’
ci sono applicazioni oltre la crittografia dove cio’ sarebbe rilevante?
l’importnate e’ che n sia uno
o che il processore con cui calcoli np sia n volte piu’ veloce di quello con cui calcoli n