Kaip daugianario laiko tikrintuvą galima konvertuoti į lygiavertę nedeterministinę Tiuringo mašiną?
Polinominį laiko tikrintuvą galima paversti lygiaverte nedeterministinė Tiuringo mašina sukūrus mašiną, kuri gali atspėti įrodymo sertifikatą ir patikrinti jį polinominiu laiku. Šis konvertavimas pagrįstas nedeterministinio skaičiavimo koncepcija, kuri leidžia mašinai vienu metu ištirti visus galimus kelius.
Norėdami suprasti šią konversiją, pirmiausia apibrėžkime, kas yra daugianario laiko tikrintuvas. Skaičiavimo sudėtingumo teorijoje daugianario laiko tikrintuvas yra deterministinė Tiuringo mašina, galinti patikrinti sprendimo problemos sprendimo teisingumą polinominiu laiku. Tam reikia dviejų įvesčių: probleminio egzemplioriaus ir įrodymo sertifikato ir nustato, ar sertifikatas yra galiojantis nurodyto egzemplioriaus įrodymas.
Dabar, norėdami paversti daugianario laiko tikrintuvą į lygiavertę nedeterministinę Tiuringo mašiną, turime atsižvelgti į nedeterministinio skaičiavimo savybes. Nedeterministinėje Tiuringo mašinoje kiekviename žingsnyje mašina gali būti kelių būsenų ir vienu metu pereiti į kelias būsenas. Tai leidžia mašinai lygiagrečiai ištirti visus galimus skaičiavimo kelius.
Norėdami konvertuoti tikrintuvą, galime sukurti nedeterministinę Tiuringo mašiną, kuri atspėtų įrodymo sertifikatą ir tada imituoja tikrintuvą visais įmanomais keliais. Jei kuris nors iš kelių priima, tada nedeterministinė mašina priima. Priešingu atveju jis atmeta.
Iliustruojame tai pavyzdžiu. Tarkime, kad turime daugianario laiko tikrintuvą grafiko spalvinimo problemai spręsti. Tikriklis kaip įvestį paima grafiką ir jo viršūnių spalvą ir patikrina, ar spalva galioja, patikrindama, ar nė viena gretima viršūnė neturi tokios pačios spalvos.
Norėdami konvertuoti šį tikrintuvą į nedeterministinę Tiuringo mašiną, sukonstruojame mašiną, kuri atspėja spalvą ir vienu metu imituoja visų galimų spalvų tikrintuvą. Jei kuris nors iš dažų atitinka spalvinimo apribojimus, tada nedeterministinė mašina tai priima. Priešingu atveju jis atmeta.
Šiame pavyzdyje nedeterministinė mašina atspėtų spalvą lygiagrečiai priskirdama spalvas viršūnėms. Tada jis imituotų kiekvieno galimo dažymo tikrintuvą ir patikrintų, ar dažymas yra tinkamas. Jei kuri nors iš modeliavimų priima, tada nedeterministinė mašina priima.
Naudodami šią konversiją matome, kad daugianario laiko tikrintuvas gali būti konvertuojamas į lygiavertę nedeterministinę Tiuringo mašiną. Šis konvertavimas leidžia mums analizuoti NP klasės (nedeterministinio daugianario laiko) uždavinių sudėtingumą, atsižvelgiant į daugianario laiko tikrintuvų egzistavimą.
Polinominį laiko tikrintuvą galima konvertuoti į lygiavertę nedeterministinę Tiuringo mašiną sukūrus mašiną, kuri atspėja įrodymo sertifikatą ir tikrina jį visais įmanomais keliais vienu metu. Šis konvertavimas leidžia analizuoti NP klasės problemų sudėtingumą.
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“.