Sprendimo uždavinių klasės P ir NP
Sprendimas per polinominį laiką ir tikrinimas per polinominį laiką skiriasi.
Esminės žinios
Klasei P priklauso sprendimo uždaviniai, kuriuos deterministinis algoritmas išsprendžia per laiką, polinominį įvesties ilgio atžvilgiu. Klasei NP priklauso uždaviniai, kurių egzemplioriams su atsakymu „taip“ egzistuoja polinominio dydžio sertifikatai, patikrinami per polinominį laiką, o egzemplioriams su atsakymu „ne“ nėra nė vieno priimamo sertifikato. P⊆NP.
Sąlygos ir taikymo ribos
- Fiksuokime įprastą diskrečiosios mašinos modelį ir aiškiai apibrėžtą baigtinį įvesties kodavimą.
- NP nereiškia „nepolinominis“; polinominiai rėžiai yra asimptotiniai, o ne praktinės spartos garantija.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Fiziniai puslapiai 2–3: sprendimas ir tikrinimas per polinominį laiką, sertifikatų sąlygos, redukcijos ir NP pilnumas.
2026-10-10 · P, NP ir tikrintuvo kvantoriai; neteigiama, kad P ir NP santykio problema išspręsta.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-complexity-p-np
- Versija
- university-reference.1
- Struktūruotas žinyno įrašas
- Universitetinis žinynas