P egyenlő-e NP?

Örülök, hogy éltetek a jelentés jogával, így törlés után, megvárva a megérdemelt, büntetésemül kapott 6 órát, újra kiírhatom a kérdést - kiegészítve magyarázatokkal azok kedvéért, akik nem tájékozottak a tudományban és nem használják a google-t, de azért feljárnak ide jelentgetni másokat. :)

A P a determinisztikus architektúrán polinomidőben eldönthető problémák osztálya.

Az NP a nemdeterminisztikus architektúrán polinomidőben eldönthető problémák osztálya.

P részhalmaza NP-nek, a kérdés, hogy ez valódi részhalmazi reláció-e. Más szóval számít-e, hogy a polinom időigényű problémák esetén, hogy az architektúra determinisztikus vagy nemdeterminisztikus-e, vagy pedig van olyan NP-teljes probléma, ami P-ben már nem oldható meg - vagyis nincs rá algoritmus.

Lásd: [link]

Egyébként, ha P=NP, akkor SAT olyan könnyűvé válik, mint a 2-SAT, a NEXP-teljes problémák megoldhatóak lesznek EXP-ben is, és sok más hasonló következmény...