P ir NP lygumas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Diagrama, rodanti sąryšį tarp sudėtingumo klasių, jei P ≠ NP

P ir NP lygumasmatematikos 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.[1] Kitaip tariant, jis klausia, ar klasė P yra lygi klasei NP.[1]

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.[1]

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).[1] Vėliau ją pradėta apibrėžti remiantis patikrinimo santykiu.[1]

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

Išnašos[redaguoti | redaguoti vikitekstą]

  1. 1,0 1,1 1,2 1,3 1,4 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.
  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]