Ar problema gali būti NP sudėtingumo klasėje, jei yra nedeterministinė tiūro mašina, kuri ją išspręs daugianario laiku
Klausimas "Ar problema gali būti NP sudėtingumo klasėje, jei yra nedeterministinė Tiuringo mašina, kuri ją išspręs daugianario laiku?" paliečia pagrindines skaičiavimo sudėtingumo teorijos sąvokas. Norėdami visapusiškai išspręsti šį klausimą, turime apsvarstyti NP sudėtingumo klasės apibrėžimus ir charakteristikas bei nedeterministinių Turingo mašinų (NDTM) vaidmenį.
NP apibrėžimas
Klasė NP (nedeterministinis daugianario laikas) susideda iš sprendimo problemų, kurių sprendimas gali būti patikrintas kaip teisingas arba neteisingas daugianario laiku deterministine Tiuringo mašina (DTM). Formaliai sprendimo problema yra NP, jei yra daugianario laiko patikrinimo algoritmas, galintis patikrinti nurodyto sertifikato (arba liudininko) teisingumą problemos atveju.
Nedeterministinės Tiuringo mašinos
Nedeterministinė Tiuringo mašina yra teorinis skaičiavimo modelis, praplečiantis deterministinės Tiuringo mašinos galimybes. Skirtingai nuo DTM, kuris eina vienu skaičiavimo keliu, apibrėžtu jo perėjimo funkcija, NDTM vienu metu gali atlikti kelis skaičiavimo kelius. Kiekviename žingsnyje NDTM gali „pasirinkti“ iš galimų perėjimų rinkinio, efektyviai išnagrinėdamas daugybę galimų skaičiavimų lygiagrečiai.
NDTM daugianario laiko išsprendžiamumas
Teigiama, kad problema gali būti išspręsta naudojant NDTM per polinominį laiką, jei yra nedeterministinis algoritmas, galintis rasti problemos sprendimą keliais žingsniais, kurie yra daugianario įvesties dydžio. Tai reiškia, kad bet kuriuo problemos atveju NDTM gali ištirti skaičiavimo kelią, kuris veda į sprendimą daugianario laiku.
Ryšys tarp NP ir NDTM
Klasė NP gali būti lygiaverčiai apibrėžta NDTM terminais. Tiksliau, sprendimo problema yra NP tada ir tik tada, kai yra NDTM, galintis išspręsti problemą daugianario laiku. Šis lygiavertiškumas atsiranda dėl to, kad NDTM gali atspėti sertifikatą nedeterministiniu būdu ir tada deterministiškai jį patikrinti daugianario laiku.
Norėdami tai iliustruoti pavyzdžiu, apsvarstykite gerai žinomą NP pilną problemą, Būlio patenkinimo problemą (SAT). Atsižvelgiant į Būlio formulę konjunktyvine normaliąja forma (CNF), užduotis yra nustatyti, ar kintamiesiems yra priskirtos tiesos reikšmės, dėl kurių formulė yra teisinga. NDTM gali išspręsti SAT daugianario laiku, nedeterministiškai atspėdamas tiesos reikšmių priskyrimą ir tada deterministiškai patikrindamas, ar priskyrimas atitinka formulę. Tikrinimo veiksmas, apimantis formulės įvertinimą pagal spėjamą priskyrimą, gali būti atliktas daugianario laiku.
NDTM daugianario laiko sprendžiamumo pasekmės
Atsižvelgdami į aukščiau pateiktus apibrėžimus ir NP ir polinominio laiko išsprendžiamumo NDTM lygiavertiškumą, galime daryti išvadą, kad jei yra NDTM, kuris išsprendžia problemą daugianario laiku, tada problema iš tikrųjų yra NP. Taip yra todėl, kad tokio NDTM egzistavimas reiškia, kad yra problemos daugianario laiko patikrinimo algoritmas. NDTM nedeterministinio spėjimo fazė atitinka sertifikato generavimą, o deterministinės patikros fazė – daugianario laiko patikros algoritmą.
Kiti svarstymai ir pavyzdžiai
Norėdami išsamiau išaiškinti šią koncepciją, panagrinėkime papildomus NP problemų pavyzdžius ir jų ryšį su NDTM:
1. Hamiltono kelio problema: Pateikus grafiką, Hamiltono kelio uždavinys klausia, ar yra kelias, kuris aplanko kiekvieną viršūnę tiksliai vieną kartą. NDTM gali išspręsti šią problemą daugianario laiku, nedeterministiškai atspėdamas viršūnių seką ir tada patikrindamas, ar seka sudaro tinkamą Hamiltono kelią. Tikrinimo veiksmas apima iš eilės einančių viršūnių gretimumo patikrinimą ir užtikrinimą, kad kiekviena viršūnė būtų aplankyta tiksliai vieną kartą, o abu gali būti atliekami daugianario laiku.
2. Pogrupio sumos problema: Atsižvelgiant į sveikųjų skaičių rinkinį ir tikslinę sumą, poaibių sumos uždavinys klausia, ar yra sveikųjų skaičių poaibis, kuris sumuojasi į tikslą. NDTM gali išspręsti šią problemą per daugianario laiką, nedeterministiškai atspėdamas sveikųjų skaičių poaibį ir tada patikrindamas, ar poaibio suma lygi tikslui. Tikrinimo veiksmas apima spėjamo poaibio elementų sumavimą, kurį galima atlikti daugianario laiku.
3. Grafiko spalvinimo problema: Atsižvelgiant į grafiką ir daugybę spalvų, grafiko spalvinimo uždavinys klausia, ar įmanoma nuspalvinti grafiko viršūnes taip, kad dvi gretimos viršūnės nebūtų tokios pačios spalvos. NDTM gali išspręsti šią problemą per daugianario laiką, nedeterministiškai priskirdamas spalvas viršūnėms ir tada patikrindamas, ar spalva yra tinkama. Tikrinimo veiksmas apima gretimų viršūnių spalvų patikrinimą, kuris gali būti atliktas daugianario laiku.
Išvada
Atsižvelgiant į pateiktus apibrėžimus ir pavyzdžius, aišku, kad problema iš tikrųjų gali būti NP sudėtingumo klasėje, jei yra nedeterministinė Tiuringo mašina, kuri ją išspręs daugianario laiku. Šis ryšys yra kertinis skaičiavimo sudėtingumo teorijos akmuo ir pabrėžia NDTM daugianario laiko išsprendžiamumo ir narystės NP klasėje lygiavertiškumą.
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?
- 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?
- Ar yra prieštaravimas tarp NP apibrėžimo kaip sprendimų problemų klasės, naudojant daugianario laiko tikrintuvus, ir to, kad P klasės uždaviniai taip pat turi daugianario laiko tikrintuvus?
Peržiūrėkite daugiau klausimų ir atsakymų skyriuje „Sudėtingumas“.