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.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. 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“ (). 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šą.Arthur M. Jaffe „The Millennium Grand Challenge in Mathematics“, „Notices of the AMS“, June/July 2000, Vol. 53, Nr. 6, p. 652-660  

 Išnašos 

Kategorija:Algoritmų teorija