Ar NP klasė gali būti lygi EXPTIME klasei?
Klausimas, ar NP klasė gali būti lygi EXPTIME klasei, gilinasi į pagrindinius skaičiavimo sudėtingumo teorijos aspektus. Norint visapusiškai atsakyti į šią užklausą, būtina suprasti šių sudėtingumo klasių apibrėžimus ir savybes, jų tarpusavio ryšius ir tokios lygybės pasekmes.
Apibrėžimai ir savybės
NP (nedeterministinis polinominis laikas):
Klasę NP sudaro sprendimo problemos, kurių duotas sprendimas polinominiu laiku gali būti patikrintas kaip teisingas arba neteisingas deterministine Tiuringo mašina. Formaliai kalba ( L ) yra NP, jei egzistuoja daugianario laiko tikrintojas ( V ) ir daugianomas ( p ), kad kiekvienai eilutei ( x in L ) yra sertifikatas ( y ) su ( |y| leq p(|x|) ) ir ( V(x, y) = 1 ).
EXPTIME (eksponentinis laikas):
Klasė EXPTIME apima sprendimo problemas, kurias gali išspręsti deterministinė Tiuringo mašina eksponentiniu laiku. Formaliai kalba ( L ) yra EXPTIME, jei egzistuoja deterministinė Tiuringo mašina ( M ) ir konstanta ( k ), kad kiekvienai eilutei ( x L ), ( M ) nusprendžia ( x ) laike ( O(2 ) ^{n^k}) ), kur ( n ) yra ( x ) ilgis.
Ryšys tarp NP ir EXPTIME
Norėdami išanalizuoti, ar NP gali būti lygus EXPTIME, turime apsvarstyti žinomus ryšius tarp šių klasių ir tokios lygybės pasekmes.
1. Sulaikymas:
Yra žinoma, kad NP yra EXPTIME. Taip yra todėl, kad bet kokia problema, kurią galima patikrinti daugianario laiku (kaip NP), taip pat gali būti išspręsta eksponentiniu laiku. Tiksliau, nedeterministinis daugianario laiko algoritmas gali būti imituojamas deterministiniu eksponentinės laiko algoritmu. Todėl (tekstas{NP} subseteq tekstas{EXPTIME}).
2. Atskyrimas:
Plačiai paplitęs tikėjimas sudėtingumo teorijoje yra tas, kad NP yra griežtai įtrauktas į EXPTIME, ty (tekstas{NP} subsetneq text{EXPTIME}). Šis įsitikinimas kyla iš to, kad NP uždaviniai gali būti išsprendžiami nedeterministiniu daugianario laiku, kuris paprastai laikomas mažesne klase nei problemos, sprendžiamos deterministiniu eksponenciniu laiku.
NP = EXPTIME pasekmės
Jei NP būtų lygus EXPTIME, tai reikštų keletą didelių pasekmių mūsų supratimui apie skaičiavimo sudėtingumą:
1. Polinomas ir eksponentinis laikas:
Lygybė (tekstas{NP} = tekstas{EXPTIME}) rodo, kad kiekviena problema, kurią galima išspręsti eksponentiniu laiku, taip pat gali būti patikrinta daugianario laiku. Tai reikštų, kad daugelis problemų, kurioms šiuo metu manoma, kad reikia eksponentinio laiko, gali būti patikrintos (taigi potencialiai išspręstos) daugianario laiku, o tai prieštarauja dabartiniams įsitikinimams sudėtingumo teorijoje.
2. Sudėtingumo klasių žlugimas:
Jei NP būtų lygus EXPTIME, tai taip pat reikštų kelių sudėtingumo klasių žlugimą. Pavyzdžiui, tai reikštų, kad (tekstas{P} = tekstas{NP}), nes NP užbaigtos problemos būtų išspręstos per daugianario laiką. Tai dar reikštų, kad (tekstas{P} = tekstas{PSPACE}) ir gali sukelti daugianario hierarchijos žlugimą.
Pavyzdžiai ir kiti svarstymai
Norėdami iliustruoti pasekmes, apsvarstykite šiuos pavyzdžius:
1. SAT (patenkinamumo problema):
SAT yra gerai žinoma NP problema. Jei NP būtų lygus EXPTIME, tai reikštų, kad SAT galima išspręsti deterministiniu eksponentiniu laiku. Dar svarbiau, tai reikštų, kad SAT galima patikrinti daugianario laiku ir tokiu būdu išspręsti daugianario laiku, todėl (tekstas{P} = tekstas{NP}).
2. Šachmatai:
Yra žinoma, kad problema, kaip nustatyti, ar žaidėjas turi laimėjimo strategiją tam tikroje šachmatų pozicijoje, yra EXPTIME. Jei NP būtų lygus EXPTIME, tai reikštų, kad tokią problemą būtų galima patikrinti daugianario laiku, o tai šiuo metu manoma, kad tai neįmanoma.
Išvada
Klausimas, ar NP klasė gali būti lygi EXPTIME klasei, yra svarbus skaičiavimo sudėtingumo teorijoje. Remiantis dabartinėmis žiniomis, manoma, kad NP yra griežtai įtrauktas į EXPTIME. Jei NP būtų lygus EXPTIME, pasekmės būtų labai didelės, o tai sukeltų kelių sudėtingumo klasių žlugimą ir iššauktų mūsų dabartinį supratimą apie daugianario ir eksponentinį laiką.
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 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?
- 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“.