" Si avvicina il sogno più antico " cit.

Quote:

---

Originally Posted by Glasny

Ci vorrà qualche mese, ora che gli altri scienziati cercano errori e l'autore li corregge, alla fine o si arriva a una dimostrazione accettata oppure si scova un errore non correggibile.

Non credo che studi informatica Hardcore, almeno lo spero. Però il problema interessa anche i non informatici, anche perchè si va dalla crittografia ai programmi per gestire il traffico aereo e anzi la maggior parte delle applicazioni interessanti si basano su problemi np-completi e loro soluzioni approssimate.

---

A me pareva facesse ingegneria informatica, magari ricordo male.. cmq sticazzi :nod:

Ti ricordo cmq che tutta la classificazione dei problemi come P, NP o NP-completi è rivolta solo e soltanto a problemi decisionali. Il che vuol dire che, anche se dovessero dimostrare in futuro che P = NP, per problemi enumerativi (che sono i più interessanti) le cose sono diverse

Quote:

---

Originally Posted by Axet

A me pareva facesse ingegneria informatica, magari ricordo male.. cmq sticazzi :nod:

Ti ricordo cmq che tutta la classificazione dei problemi come P, NP o NP-completi è rivolta solo e soltanto a problemi decisionali. Il che vuol dire che, anche se dovessero dimostrare in futuro che P = NP, per problemi enumerativi (che sono i più interessanti) le cose sono diverse

---

Se il metodo usato nella dimostrazione viene confermato, vedrai che si estende anche per dimostrare altre cose più o meno correlate.

Nono io intendevo proprio che, nel caso venga dimostrato il contrario rispetto a quel paper, cioè che P = NP, ancora non avremmo in mano un cazzo di niente. I problemi decisionali sono meno complessi dei problemi enumerativi.

Prendiamo SAT che è quello che è servito per dimostrare l'esistenza degli NP-completi. Il problema decisionale chiede, data una formula espressa secondo le regole di SAT, se questa sia o meno soddisfacibile. Se lo è risponde true, se non lo è risponde false. Questo problema è NP-completo ed è come abbiamo appena visto un problema decisionale. Pensala in un'altra maniera: data la formula non voglio più sapere se sia soddisfacibile o meno, voglio sapere quali sono tutte le configurazioni che la soddisfano. Risulta evidente che il secondo problema risulti molto più pesante del primo.

Difatti questa variante di SAT non è manco NP-completa, bensì NP-hard (in quanto non è decisionale ma enumerativa)

Quote:

---

Originally Posted by Axet

Nono io intendevo proprio che, nel caso venga dimostrato il contrario rispetto a quel paper, cioè che P = NP, ancora non avremmo in mano un cazzo di niente. I problemi decisionali sono meno complessi dei problemi enumerativi.

Prendiamo SAT che è quello che è servito per dimostrare l'esistenza degli NP-completi. Il problema decisionale chiede, data una formula espressa secondo le regole di SAT, se questa sia o meno soddisfacibile. Se lo è risponde true, se non lo è risponde false. Questo problema è NP-completo ed è come abbiamo appena visto un problema decisionale. Pensala in un'altra maniera: data la formula non voglio più sapere se sia soddisfacibile o meno, voglio sapere quali sono tutte le configurazioni che la soddisfano. Risulta evidente che il secondo problema risulti molto più pesante del primo.

Difatti questa variante di SAT non è manco NP-completa, bensì NP-hard (in quanto non è decisionale ma enumerativa)

---

Non si diceva np-arduo (l'ho studiato anni fa magari a quei tempi si usava ancora l'italiano) ?

Dubito ormai si dimostri il contrario, se leggi almeno l'abstract e le critiche ti rendi conto che probabilmente corregge tutto e la questione viene chiusa. Lo so che non tutti i problemi in NP sono NP-completi ma nella pratica mi dici perchè i problemi NP-ardui sarebbero più interessanti ? Visto che nelle applicazioni pratiche ne trovo quanti ne voglio di esempi di problemi np-completi, ma quelli ardui non mi pare.

Perchè con np e np-completi ma come anche con p, p-space e np-space (dove tra l'altro per questi due è stata già dimostrata l'ugaglianza) si parla di problemi decisionali. Parafrasando, tu chiedi al computer se il calcolo che hai fatto è giusto e lui ti dice si o no.
Sarebbe più interessante sapere direttamente la risposta alla domanda piuttosto che trovare la risposta e poi chiedere se sia o meno corretta.

Questi rimangono problemi non polinomiali, non c'è un cazzo da fare.. il dubbio sull'uguaglianza tra P e NP verteva sul fatto che essendo problemi decisionali magari c'era qualche modo, ancora sconosciuto, per rendere la computazione più veloce al fine di trovare la risposta. Ma se devi invece enumerare tutte le possibilità, non ci sono cazzi che tengano le devi vagliare tutte.. e per problemi non polinomiali queste sono, appunto, non polinomiali.

edit:
np-hard, np-difficile e np-arduo sono sinonimi