P ir NP lygumas

P ir NP lygumas – matematikos uždavinys, kuriame prašoma nustatyti, ar kiekviena formali kalba, priimama nedeterministinės Tiuringo mašinos per polinominį laiką taip pat gali būti per polinominį laiką priimta ir deterministinės Tiuringo mašinos. Kitaip tariant, jis klausia, ar klasė P yra lygi klasei 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

Stephen Cook „The P versus NP Problem“ // James Carlson, Arthur Jaffe, Andrew Wiles (red.) „The Millennium Prize Problems“, „American Mathematical Society“, 2006, 87-104 psl.
Arthur M. Jaffe „The Millennium Grand Challenge in Mathematics“, „Notices of the AMS“, June/July 2000, Vol. 53, Nr. 6, p. 652-660 [1] Archyvuota kopija 2018-06-27 iš Wayback Machine projekto.

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

[StephenCook_2006-1] Stephen Cook „The P versus NP Problem“ // James Carlson, Arthur Jaffe, Andrew Wiles (red.) „The Millennium Prize Problems“, „American Mathematical Society“, 2006, 87-104 psl.

[Jaffe_2000-2] Arthur M. Jaffe „The Millennium Grand Challenge in Mathematics“, „Notices of the AMS“, June/July 2000, Vol. 53, Nr. 6, p. 652-660 [1] Archyvuota kopija 2018-06-27 iš Wayback Machine projekto.