From Wikipedia, the free encyclopedia
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.[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]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.