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.
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.
Sprendimo uždavinys B yra NP sunkus, jei kiekvienas NP klasės uždavinys gali būti redukuotas į B per polinominį laiką. B yra NP pilnas, jei jis taip pat priklauso NP klasei. Polinominis algoritmas bet kuriam NP pilnam uždaviniui leistų gauti polinominius algoritmus visiems NP klasės uždaviniams.
Fiksuotą deterministinę Tiuringo mašiną su baigtiniu juostų skaičiumi, veikiančią per laiką t(n)≥n, galima imituoti vienajuoste mašina per O(t(n)²) laiką, saugant juostų turinį bei galvučių žymeklius ir peržiūrint juos kiekviename imituojamame žingsnyje. Šių modelių sprendžiamų kalbų aibės ir polinominio laiko klasė sutampa.
L⊆NL⊆P⊆NP⊆PSPACE=NPSPACE⊆EXP, kur EXP=⋃ₖ≥₁DTIME(2ⁿᵏ). Sustojanti mašina, naudojanti polinominį atminties kiekį, turi tik eksponentinį konfigūracijų skaičių; logaritminę atmintį naudojančios mašinos konfigūracijų grafas yra polinominio dydžio. Pagal deterministinę laiko hierarchiją P⊊EXP.
Būlio formulių įvykdomumo uždavinys SAT yra NP pilnas pagal polinominio laiko daugelio į vieną redukcijas. Kiekvienai kalbai A∈NP ir įvesčiai x polinominio dydžio formulė koduoja polinominio laiko priimančio skaičiavimo lentelę taip, kad x∈A tada ir tik tada, kai ši formulė yra įvykdoma; pats formulę tenkinantis reikšmių priskyrimas yra NP liudijimas.
Interaktyvus įrodymas leidžia polinominiu laiku veikiančiam atsitiktinumą naudojančiam tikrintojui keistis pranešimais su skaičiavimo ištekliais neapribotu įrodinėtoju. Pilnumas užtikrina sėkmingą sąžiningą įrodinėtoją teigiamuose uždavinio egzemplioriuose; pagrįstumas riboja priėmimo tikimybę kiekvienam sukčiaujančiam įrodinėtojui neigiamuose egzemplioriuose. Kartojimas ir tikimybinių garantijų stiprinimas turi išlaikyti protokolo modelį. Tuo tarpu argumentas riboja tik skaičiavimo ištekliais apribotus sukčiaujančius įrodinėtojus, todėl būtina nurodyti jo skaičiavimo sunkumo prielaidas ir išteklių ribas.
Proof verification is a resource-defined decision procedure.
Redukcija paverčia sėkmingą schemos puolėją nurodytos prielaidos puolėju, aiškiai susiedama laiką, užklausų skaičių ir sėkmės tikimybę. Hibridinis argumentas sumuoja nuoseklių žaidimų atskyrimo skirtumus; daugiklis q ar papildoma nesėkmės tikimybė gali reikšmingai pakeisti baigtinių parametrų saugumą. Nykstamas mažumas yra asimptotinė sąlyga, o ne tikslus vieno rakto dydžio saugumo stiprumo bitais sertifikatas; atsitiktinis orakulas yra modelis, o ne teorema, kad kiekviena maišos funkcija elgiasi atsitiktinai.
Worst-case complexity classes do not directly establish an average-case cryptographic assumption.