Kan 'n probleem in NP-kompleksiteitsklas wees as daar 'n nie-deterministiese draaimasjien is wat dit in polinoomtyd sal oplos
Die vraag "Kan 'n probleem in NP-kompleksiteitsklas wees as daar 'n nie-deterministiese Turing-masjien is wat dit in polinoomtyd sal oplos?" raak fundamentele konsepte in berekeningskompleksiteitsteorie aan. Om hierdie vraag volledig aan te spreek, moet ons die definisies en kenmerke van die NP-kompleksiteitsklas en die rol van nie-deterministiese Turing-masjiene (NDTM's) oorweeg.
Definisie van NP
Die klas NP (nie-deterministiese polinoomtyd) bestaan uit besluitnemingsprobleme waarvoor 'n gegewe oplossing as korrek of verkeerd in polinoomtyd geverifieer kan word deur 'n deterministiese Turing-masjien (DTM). Formeel is 'n besluitprobleem in NP as daar 'n polinoom-tyd verifikasie-algoritme bestaan wat die korrektheid van 'n gegewe sertifikaat (of getuie) vir 'n geval van die probleem kan verifieer.
Nie-deterministiese Turing-masjiene
'n Nie-deterministiese Turing-masjien is 'n teoretiese model van berekening wat die vermoëns van 'n deterministiese Turing-masjien uitbrei. Anders as 'n DTM, wat 'n enkele berekeningspad volg wat deur sy oorgangsfunksie gedefinieer word, kan 'n NDTM verskeie berekeningspaaie gelyktydig volg. By elke stap kan 'n NDTM "kies" uit 'n stel moontlike oorgange, en effektief baie moontlike berekeninge in parallel ondersoek.
Polinoom-tydoplosbaarheid deur NDTM'e
Daar word gesê dat 'n probleem deur 'n NDTM in polinoomtyd opgelos kan word as daar 'n nie-deterministiese algoritme bestaan wat 'n oplossing vir die probleem kan vind binne 'n aantal stappe wat polinoom is in die grootte van die inset. Dit beteken dat vir enige geval van die probleem, die NDTM 'n berekeningspad kan verken wat lei tot 'n oplossing in polinoomtyd.
Verwantskap tussen NP en NDTM'e
Die klas NP kan ekwivalent in terme van NDTM'e gedefinieer word. Spesifiek, 'n besluitnemingsprobleem is in NP as en slegs as daar 'n NDTM bestaan wat die probleem in polinoomtyd kan oplos. Hierdie ekwivalensie spruit uit die feit dat 'n NDTM 'n sertifikaat nie-deterministies kan raai en dit dan deterministies in polinoomtyd kan verifieer.
Om dit met 'n voorbeeld te illustreer, oorweeg die bekende NP-volledige probleem, die Boole-bevredigingsprobleem (SAT). Gegewe 'n Boole-formule in konjunktiewe normale vorm (CNF), is die taak om te bepaal of daar 'n toewysing van waarheidswaardes aan die veranderlikes bestaan wat die formule waar maak. 'n NDTM kan SAT in polinoomtyd oplos deur 'n toewysing van waarheidswaardes nie-deterministies te raai en dan deterministies na te gaan of die opdrag aan die formule voldoen. Die verifikasiestap, wat die evaluering van die formule onder die geraaide opdrag behels, kan in polinoomtyd gedoen word.
Implikasies van polinoom-tydoplosbaarheid deur NDTM'e
Gegewe die bogenoemde definisies en die ekwivalensie tussen NP en polinoom-tyd-oplosbaarheid deur NDTM'e, kan ons aflei dat as daar 'n NDTM bestaan wat 'n probleem in polinoomtyd oplos, dan is die probleem inderdaad in NP. Dit is omdat die bestaan van so 'n NDTM impliseer dat daar 'n polinoom-tyd verifikasie algoritme vir die probleem is. Die nie-deterministiese raaifase van die NDTM stem ooreen met die generering van 'n sertifikaat, en die deterministiese verifikasiefase stem ooreen met die polinoom-tyd verifikasie algoritme.
Verdere oorwegings en voorbeelde
Om hierdie konsep verder toe te lig, kom ons kyk na bykomende voorbeelde van probleme in NP en hul verhouding met NDTM'e:
1. Hamiltoniaanse padprobleem: Gegewe 'n grafiek, vra die Hamiltoniaanse Pad-probleem of daar 'n pad bestaan wat elke hoekpunt presies een keer besoek. 'n NDTM kan hierdie probleem in polinoomtyd oplos deur 'n reeks hoekpunte nie-deterministies te raai en dan te verifieer of die ry 'n geldige Hamiltoniaanse pad vorm. Die verifikasiestap behels die nagaan van die nabyheid van opeenvolgende hoekpunte en om te verseker dat elke hoekpunt presies een keer besoek word, wat albei in polinoomtyd gedoen kan word.
2. Subset Som Probleem: Gegewe 'n stel heelgetalle en 'n teikensom, vra die Subset Som-probleem of daar 'n subset van die heelgetalle bestaan wat tot die teiken som. 'n NDTM kan hierdie probleem in polinoomtyd oplos deur 'n subset van die heelgetalle nie-deterministies te raai en dan te verifieer of die som van die subset gelyk is aan die teiken. Die verifikasiestap behels die opsomming van die elemente van die geraaide subset, wat in polinoomtyd gedoen kan word.
3. Grafiekkleurprobleem: Gegewe 'n grafiek en 'n aantal kleure, vra die Grafiekkleurprobleem of dit moontlik is om die hoekpunte van die grafiek so in te kleur dat geen twee aangrensende hoekpunte dieselfde kleur deel nie. 'n NDTM kan hierdie probleem in polinoomtyd oplos deur nie-deterministies kleure aan die hoekpunte toe te ken en dan te verifieer of die kleuring geldig is. Die verifikasiestap behels die kontrolering van die kleure van aangrensende hoekpunte, wat in polinoomtyd gedoen kan word.
Gevolgtrekking
In die lig van die definisies en voorbeelde wat verskaf word, is dit duidelik dat 'n probleem wel in die NP-kompleksiteitsklas kan wees as daar 'n nie-deterministiese Turing-masjien bestaan wat dit in polinoomtyd sal oplos. Hierdie verhouding is 'n hoeksteen van berekeningskompleksiteitsteorie en beklemtoon die ekwivalensie tussen polinoom-tyd-oplosbaarheid deur NDTM'e en lidmaatskap in die NP-klas.
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?
- NP is die klas tale wat polinoomtydverifieerders het
- Is P en NP eintlik dieselfde kompleksiteitsklas?
- Is elke konteks vrye taal in die P-kompleksiteitsklas?
- Is daar 'n teenstrydigheid tussen die definisie van NP as 'n klas besluiteprobleme met polinoom-tyd-verifieerders en die feit dat probleme in die klas P ook polinoom-tyd-verifieerders het?
Sien meer vrae en antwoorde in Complexity