P ir NP lygumas matematikos uždavinys kuriame prašoma nustatyti ar kiekviena formali kalba priimama per taip pat gali bū

P ir NP lygumas – matematikos uždavinys, kuriame prašoma nustatyti, ar kiekviena formali kalba, priimama per taip pat gali būti per polinominį laiką priimta ir . Kitaip tariant, jis klausia, ar klasė yra lygi klasei .

Diagrama, rodanti sąryšį tarp sudėtingumo klasių, jei P ≠ NP

Neformaliai klasei P priskiriami uždaviniai, kuriuose reikia priimti sprendimą, kurie yra išsprendžiami per skaičių žingsnių, kuris ribojamas kokio nors daugianario, priklausančio nuo įėjimo duomenų ilgio.

Klasė NP iš pradžių buvo apibrėžiama remiantis nedeterministinėmis Tiuringo mašinomis, nuo to ir pavadinimas gautas sutrumpinus „nedeterministinis polinominis laikas“ (angl. nondeterministic polynomial time). Vėliau ją pradėta apibrėžti remiantis patikrinimo santykiu.

P ir NP lygumas buvo vienas iš septynių uždavinių, kurie 2000 m. buvo įtraukti į Tūkstantmečio premijos uždavinių sąrašą.

Išnašos

„The P versus NP Problem“ // , , (red.) „The Millennium Prize Problems“, „American Mathematical Society“, 2006, 87-104 psl.
Arthur M. Jaffe „The Millennium Grand Challenge in Mathematics“, „“, June/July 2000, Vol. 53, Nr. 6, p. 652-660 [1]

Šis su matematika susijęs straipsnis yra . Jūs galite prisidėti prie Vikipedijos papildydami šį straipsnį.

[StephenCook_2006-1] „The P versus NP Problem“ // , , (red.) „The Millennium Prize Problems“, „American Mathematical Society“, 2006, 87-104 psl.

[Jaffe_2000-2] Arthur M. Jaffe „The Millennium Grand Challenge in Mathematics“, „“, June/July 2000, Vol. 53, Nr. 6, p. 652-660 [1]