Hoe kan 'n polinoomtydverifieerder in 'n ekwivalente nie-deterministiese Turing-masjien omgeskakel word?
'n Polinoomtydverifieerder kan in 'n ekwivalente nie-deterministiese Turing-masjien omgeskakel word deur 'n masjien te bou wat die bewyssertifikaat kan raai en dit in polinoomtyd kan verifieer. Hierdie omskakeling is gebaseer op die konsep van nie-deterministiese berekening, wat die masjien toelaat om alle moontlike paaie gelyktydig te verken.
Om hierdie omskakeling te verstaan, kom ons definieer eers wat 'n polinoomtydverifieerder is. In berekeningskompleksiteitsteorie is 'n polinoomtydverifieerder 'n deterministiese Turing-masjien wat die korrektheid van 'n oplossing vir 'n besluitprobleem in polinoomtyd kan verifieer. Dit neem twee insette: die probleemgeval en 'n bewyssertifikaat, en bepaal of die sertifikaat 'n geldige bewys vir die gegewe geval is.
Nou, om 'n polinoom tydverifieerder te omskep in 'n ekwivalente nie-deterministiese Turing-masjien, moet ons die eienskappe van nie-deterministiese berekening oorweeg. In 'n nie-deterministiese Turing-masjien, by elke stap, kan die masjien in verskeie toestande wees en kan gelyktydig na verskeie toestande oorgaan. Dit stel die masjien in staat om alle moontlike paaie van berekening parallel te verken.
Om die verifieerder om te skakel, kan ons 'n nie-deterministiese Turing-masjien bou wat die bewyssertifikaat raai en dan die verifieerder op alle moontlike paaie simuleer. As enige van die paaie aanvaar, dan aanvaar die nie-deterministiese masjien. Andersins verwerp dit.
Kom ons illustreer dit met 'n voorbeeld. Gestel ons het 'n polinoomtydverifieerder vir die probleem van grafiekkleuring. Die verifieerder neem as invoer 'n grafiek en 'n kleur van sy hoekpunte, en dit kontroleer of die kleur geldig is deur te verifieer dat geen aangrensende hoekpunte dieselfde kleur het nie.
Om hierdie verifieerder in 'n nie-deterministiese Turing-masjien te omskep, bou ons 'n masjien wat 'n kleursel raai en dan die verifieerder op alle moontlike kleure gelyktydig simuleer. As enige van die kleure aan die kleurbeperkings voldoen, aanvaar die nie-deterministiese masjien. Andersins verwerp dit.
In hierdie voorbeeld sal die nie-deterministiese masjien 'n kleur raai deur kleure parallel aan die hoekpunte toe te ken. Dit sal dan die verifieerder op elk van die moontlike kleure simuleer, en kyk of die kleur geldig is. As enige van die simulasies aanvaar, dan aanvaar die nie-deterministiese masjien.
Deur hierdie omskakeling te gebruik, kan ons sien dat 'n polinoom tydverifieerder in 'n ekwivalente nie-deterministiese Turing-masjien omgeskakel kan word. Hierdie omskakeling stel ons in staat om die kompleksiteit van probleme in die klas NP (nie-deterministiese polinoomtyd) te ontleed deur die bestaan van polinoomtydverifieerders in ag te neem.
'n Polinoomtydverifieerder kan in 'n ekwivalente nie-deterministiese Turing-masjien omgeskakel word deur 'n masjien te bou wat die bewyssertifikaat raai en dit op alle moontlike paaie gelyktydig verifieer. Hierdie omskakeling stel ons in staat om die kompleksiteit van probleme in die klas NP te analiseer.
Ander onlangse vrae en antwoorde t.o.v Kompleksiteit:
- Is PSPACE-klas nie gelyk aan die EXPSPACE-klas nie?
- Is P-kompleksiteitsklas 'n subset van PSPACE-klas?
- Kan ons bewys dat Np en P-klas dieselfde is deur 'n doeltreffende polinoomoplossing vir enige NP-volledige probleem op 'n deterministiese TM te vind?
- Kan die NP-klas gelyk wees aan die EXPTIME-klas?
- Is daar probleme in PSPACE waarvoor daar geen bekende NP-algoritme is nie?
- Kan 'n SAT-probleem 'n volledige NP-probleem wees?
- Kan 'n probleem in NP-kompleksiteitsklas wees as daar 'n nie-deterministiese draaimasjien is wat dit in polinoomtyd sal oplos
- NP is die klas tale wat polinoomtydverifieerders het
- Is P en NP eintlik dieselfde kompleksiteitsklas?
- Is elke konteks vrye taal in die P-kompleksiteitsklas?
Sien meer vrae en antwoorde in Complexity