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šą.
vikipedija, wiki, enciklopedija, knyga, biblioteka, straipsnis, skaityti, nemokamas atsisiuntimas, informacija apie P ir NP lygumas, Kas yra P ir NP lygumas? Ką reiškia P ir NP lygumas?