P=NP

[mart002]

ciao a tutti,sono nuovo in questo forum e volevo chiedervi una cosa.
se si riuscisse a dimostrare che:

SAT (Boolean satisfiability problem) appartiene alla classe P,

allora risulterebbe vera la relazione P=NP ?

grazie in anticipo.

[claw91]

Al primo semestre della magistrale in informatica ci hanno erogato un corso che in una breve sua parte ha trattato di calcolabilità e complessità computazionale.

Purtroppo il docente - seppure sicuramente competente - si è rivelato non altrettanto abile nell'imprescindibile capacità, a mio avviso, di trasmettere efficacemente i concetti.

A me il suddetto argomento è parso assai interessante, anche se sicuramente molto complesso, e francamente mi è dispiaciuto non poter cogliere molto dalle lezioni seguite.

Da quello che però mi era parso di intuire, in soldoni, esiste una dimostrazione che, se trovata, praticamente sancirebbe l'inutilità del calcolo parallelo... estremizzando come se CPU dual, quad, esa e octa core sono tutte fandonie inutili.

Questo è quello che mi ha fatto capire il prof, sostenendo che al momento la comunità scientifica ritiene molto improbabile ciò sia possibile... qualcuno saprebbe spiegarmi meglio?

Sono molto curioso di capire questa faccenda, perché ovviamente si tratterebbe di una vera e propria rivoluzione