Popíšte proces konštrukcie polynómového časového overovača z polynomického nedeterministického Turingovho stroja.
Polynomiálny časový verifikátor môže byť skonštruovaný z polynomiálneho časového nedeterministického Turingovho stroja (NTM) sledovaním systematického procesu. Na pochopenie tohto procesu je nevyhnutné jasne porozumieť konceptom teórie zložitosti, najmä triedam P a NP, a pojmom polynomiálnej overiteľnosti.
V teórii výpočtovej zložitosti sa P vzťahuje na triedu rozhodovacích problémov, ktoré môže vyriešiť deterministický Turingov stroj v polynomiálnom čase. Na druhej strane, NP sa vzťahuje na triedu rozhodovacích problémov, ktorých riešenie môže byť overené v polynomiálnom čase deterministickým Turingovým strojom. Kľúčový rozdiel medzi týmito dvoma triedami je v tom, že P predstavuje problémy, ktoré možno efektívne vyriešiť, zatiaľ čo NP predstavuje problémy, ktoré možno efektívne overiť.
Verifikátor polynomiálneho času je deterministický Turingov stroj, ktorý dokáže overiť správnosť riešenia NP úlohy v polynomiálnom čase. Proces konštrukcie takéhoto overovateľa z NTM v polynomickom čase zahŕňa nasledujúce kroky:
1. Vzhľadom na NP problém, povedzme problém X, predpokladáme existenciu polynomického času NTM M, ktorý dokáže vyriešiť X. Tento NTM M má niekoľko výpočtových vetiev, z ktorých každá predstavuje inú možnú cestu vykonania.
2. Simuláciou správania NTM M zostrojíme polynomiálny časový verifikátor V pre problém X. Verifikátor V má dva vstupy: riešenie problému X a certifikát. Certifikát je dôkazom správnosti riešenia.
3. Overovateľ V najskôr skontroluje, či má certifikát platný formát. Tento krok je možné vykonať v polynomickom čase, pretože overovateľ pozná očakávanú štruktúru certifikátu.
4. Ďalej overovač V simuluje správanie NTM M na danom riešení a certifikáte. Vykonáva všetky možné vetvy výpočtu M, pričom kontroluje, či niektorá vetva prijíma vstup. Táto simulácia môže byť vykonaná v polynomiálnom čase, pretože NTM M beží v polynomiálnom čase.
5. Ak overovateľ V nájde aspoň jednu akceptujúcu vetvu výpočtu, akceptuje vstup. To znamená, že riešenie je overené ako správne pre problém X. V opačnom prípade, ak žiadna z vetiev neakceptuje, overovateľ odmietne vstup.
Kľúčovou myšlienkou konštrukcie polynomiálneho časového overovača je, že NTM M dokáže uhádnuť správny certifikát v polynómovom čase. Simuláciou správania M a kontrolou všetkých možných vetiev môže overovateľ V efektívne overovať správnosť riešenia.
Uveďme si príklad na ilustráciu tohto procesu. Zvážte problém určenia, či daný graf má Hamiltonov cyklus, čo je NP-úplný problém. Predpokladáme existenciu polynomického času NTM M, ktorý môže tento problém vyriešiť.
Aby sme skonštruovali polynomiálny časový verifikátor V pre tento problém, simulujeme správanie M na danom grafe a certifikáte. Overovateľ skontroluje, či certifikát predstavuje platný hamiltonovský cyklus overením, že navštívi každý vrchol presne raz a vytvorí cyklus.
Vyčerpávajúcou simuláciou všetkých možných vetiev výpočtu M môže overovateľ efektívne určiť, či daný graf má hamiltonovský cyklus. Ak aspoň jedna vetva M akceptuje vstup, overovateľ akceptuje vstup ako platný hamiltonovský cyklus. V opačnom prípade zadanie odmietne.
Konštrukcia polynomiálneho časového overovača z polynomiálneho časového NTM zahŕňa simuláciu správania NTM a kontrolu všetkých možných odvetví výpočtu. Tento proces umožňuje efektívne overovanie riešení NP problémov. Konštrukciou takýchto verifikátorov môžeme klasifikovať problémy na základe ich overiteľnosti v polynomiálnom čase.
Ďalšie nedávne otázky a odpovede týkajúce sa zložitosť:
- Nerovná sa trieda PSPACE triede EXPSPACE?
- Je trieda zložitosti P podmnožinou triedy PSPACE?
- Môžeme dokázať, že Np a P trieda sú rovnaké nájdením efektívneho polynomického riešenia pre akýkoľvek NP úplný problém na deterministickom TM?
- Môže sa trieda NP rovnať triede EXPTIME?
- Vyskytujú sa v PSPACE problémy, pre ktoré nie je známy NP algoritmus?
- Môže byť problém SAT úplným problémom NP?
- Môže byť problém v triede zložitosti NP, ak existuje nedeterministický Turingov stroj, ktorý ho vyrieši v polynomiálnom čase
- NP je trieda jazykov, ktoré majú polynomiálne časové overovače
- Sú P a NP vlastne rovnaká trieda zložitosti?
- Je každý jazyk bez kontextu v triede zložitosti P?
Pozrite si ďalšie otázky a odpovede v časti Zložitosť