Apibūdinkite daugianario laiko tikrintuvo konstravimo iš daugianario laiko nedeterministinės Tiuringo mašinos procesą.
Polinominio laiko tikrintuvas gali būti sudarytas iš daugianario laiko nedeterministinės Tiuringo mašinos (NTM), taikant sisteminį procesą. Norint suprasti šį procesą, būtina aiškiai suprasti sudėtingumo teorijos sąvokas, ypač P ir NP klases, ir daugianario patikrinamumo sąvoką.
Skaičiavimo sudėtingumo teorijoje P reiškia sprendimų problemų, kurias gali išspręsti deterministinė Tiuringo mašina daugianario laiku, klasę. Kita vertus, NP reiškia sprendimų problemų klasę, kurios sprendimą polinominiu laiku galima patikrinti deterministine Tiuringo mašina. Pagrindinis skirtumas tarp šių dviejų klasių yra tas, kad P reiškia problemas, kurias galima efektyviai išspręsti, o NP reiškia problemas, kurias galima efektyviai patikrinti.
Polinominio laiko tikrintuvas yra deterministinė Tiuringo mašina, galinti patikrinti NP uždavinio sprendimo teisingumą polinominiu laiku. Tokio tikrintuvo kūrimo iš daugianario laiko NTM procesas apima šiuos veiksmus:
1. Pateikus NP uždavinį, tarkime uždavinį X, darome prielaidą, kad egzistuoja daugianario laikas NTM M, kuris gali išspręsti X. Šis NTM M turi keletą skaičiavimo šakų, kurių kiekviena reiškia skirtingą galimą vykdymo kelią.
2. Sukonstruojame X uždavinio daugianario laiko tikrintuvą V, imituodami NTM M elgseną. Tikriklis V įveda du įėjimus: problemos X sprendimą ir sertifikatą. Sertifikatas yra įrodymas, kad sprendimas yra teisingas.
3. V tikrintojas pirmiausia patikrina, ar sertifikato formatas yra tinkamas. Šį veiksmą galima atlikti daugianario laiku, nes tikrintojas žino numatomą sertifikato struktūrą.
4. Toliau tikrintuvas V imituoja NTM M elgseną duotame sprendime ir sertifikate. Jis vykdo visas įmanomas M skaičiavimo šakas, tikrindamas, ar kuri nors šaka priima įvestį. Šį modeliavimą galima atlikti daugianario laiku, nes NTM M veikia daugianario laiku.
5. Jei tikrintojas V randa bent vieną priimančią skaičiavimo šaką, jis priima įvestį. Tai reiškia, kad X problemos sprendimas yra patikrintas. Priešingu atveju, jei nė viena šaka nepriima, tikrintojas atmeta įvestį.
Pagrindinė daugianario laiko tikrintuvo kūrimo idėja yra ta, kad NTM M gali atspėti teisingą sertifikatą polinominiu laiku. Imituodamas M elgseną ir patikrindamas visas įmanomas šakas, tikrintojas V gali efektyviai patikrinti sprendimo teisingumą.
Paimkime pavyzdį šiam procesui iliustruoti. Apsvarstykite problemą, kaip nustatyti, ar tam tikrame grafike yra Hamiltono ciklas, o tai yra NP užbaigta problema. Darome prielaidą, kad egzistuoja daugianario laikas NTM M, kuris gali išspręsti šią problemą.
Norėdami sukurti daugianario laiko tikrintuvą V šiai problemai, modeliuojame M elgseną duotame grafike ir sertifikate. Tikrintojas patikrina, ar sertifikatas atitinka galiojantį Hamiltono ciklą, patikrindamas, ar jis tiksliai vieną kartą aplanko kiekvieną viršūnę ir sudaro ciklą.
Išsamiai imituodamas visas įmanomas M skaičiavimo šakas, tikrintojas gali efektyviai nustatyti, ar duotame grafike yra Hamiltono ciklas. Jei bent viena M šaka priima įvestį, tikrintojas priima įvestį kaip galiojantį Hamiltono ciklą. Priešingu atveju jis atmeta įvestį.
Sukūrus daugianario laiko tikrintuvą iš daugianario laiko NTM, reikia modeliuoti NTM elgesį ir patikrinti visas įmanomas skaičiavimo šakas. Šis procesas leidžia efektyviai patikrinti NP problemų sprendimus. Sukūrę tokius tikrintuvus, galime klasifikuoti problemas pagal jų patikrinamumą daugianario laiku.
Kiti naujausi klausimai ir atsakymai apie sudėtingumas:
- Ar PSPACE klasė nėra lygi EXPSPACE klasei?
- Ar P sudėtingumo klasė yra PSPACE klasės poaibis?
- Ar galime įrodyti, kad Np ir P klasės yra vienodos, rasdami veiksmingą daugianario sprendimą bet kuriai NP užbaigtai problemai deterministinėje TM?
- Ar NP klasė gali būti lygi EXPTIME klasei?
- Ar PSPACE yra problemų, kurioms nėra žinomo NP algoritmo?
- Ar SAT problema gali būti visiška NP problema?
- Ar problema gali būti NP sudėtingumo klasėje, jei yra nedeterministinė tiūro mašina, kuri ją išspręs daugianario laiku
- NP yra kalbų, turinčių daugianario laiko tikrintuvus, klasė
- Ar iš tikrųjų P ir NP yra ta pati sudėtingumo klasė?
- Ar P sudėtingumo klasėje kiekviena kalba be konteksto?
Peržiūrėkite daugiau klausimų ir atsakymų skyriuje „Sudėtingumas“.