Ali je lahko razred NP enak razredu EXPTIME?
Vprašanje, ali je razred NP lahko enak razredu EXPTIME, se poglobi v temeljne vidike teorije računalniške kompleksnosti. Za celovito obravnavo te poizvedbe je bistveno razumeti definicije in lastnosti teh kompleksnih razredov, odnose med njimi in posledice takšne enakosti.
Definicije in lastnosti
NP (nedeterministični polinomski čas):
Razred NP sestavljajo odločitveni problemi, za katere je dano rešitev mogoče preveriti kot pravilno ali nepravilno v polinomskem času s pomočjo determinističnega Turingovega stroja. Formalno je jezik ( L ) v NP, če obstaja polinomsko časovno preverjanje ( V ) in polinom ( p ), tako da za vsak niz ( x v L ) obstaja potrdilo ( y ) z ( |y| leq p(|x|) ) in ( V(x, y) = 1 ).
EXPTIME (eksponentni čas):
Razred EXPTIME vključuje odločitvene probleme, ki jih je mogoče rešiti z determinističnim Turingovim strojem v eksponentnem času. Formalno je jezik ( L ) v EXPTIME, če obstajata deterministični Turingov stroj ( M ) in konstanta ( k ), taka da za vsak niz ( x v L ) ( M ) odloči ( x ) v času ( O(2 ^{n^k})), kjer je (n) dolžina (x).
Razmerje med NP in EXPTIME
Za analizo, ali je NP lahko enako EXPTIME, moramo upoštevati znane odnose med temi razredi in posledice takšne enakosti.
1. Vsebovanje:
Znano je, da je NP vsebovan v EXPTIME. To je zato, ker je vsak problem, ki ga je mogoče preveriti v polinomskem času (kot v NP), mogoče rešiti tudi v eksponentnem času. Natančneje, nedeterministični polinomski časovni algoritem je mogoče simulirati z determinističnim eksponentnim časovnim algoritmom. Zato (besedilo{NP} subseteq besedilo{EXPTIME}).
2. Ločitev:
Splošno razširjeno prepričanje v teoriji kompleksnosti je, da je NP strogo vključen v EXPTIME, tj. (besedilo{NP} subsetneq besedilo{EXPTIME}). To prepričanje izhaja iz dejstva, da so problemi NP rešljivi v nedeterminističnem polinomskem času, ki se na splošno šteje za manjši razred kot problemi, rešljivi v determinističnem eksponentnem času.
Posledice NP = EXPTIME
Če bi bilo NP enako EXPTIME, bi to pomenilo več globokih posledic za naše razumevanje računalniške kompleksnosti:
1. Polinom v primerjavi z eksponentnim časom:
Enakost (besedilo{NP} = besedilo{EXPTIME}) bi nakazovala, da je vsak problem, ki ga je mogoče rešiti v eksponentnem času, mogoče preveriti tudi v polinomskem času. To bi pomenilo, da bi lahko veliko težav, za katere se trenutno domneva, da zahtevajo eksponentni čas, namesto tega preverili (in s tem potencialno rešili) v polinomskem času, kar je v nasprotju s trenutnimi prepričanji v teoriji kompleksnosti.
2. Strnitev razredov kompleksnosti:
Če bi bilo NP enako EXPTIME, bi to pomenilo tudi kolaps več kompleksnih razredov. To bi na primer pomenilo, da (besedilo{P} = besedilo{NP}), saj bi bili NP-popolni problemi rešljivi v polinomskem času. To bi nadalje impliciralo, da (besedilo{P} = besedilo{PSPACE}) in potencialno vodilo do sesutja polinomske hierarhije.
Primeri in nadaljnji premisleki
Za ponazoritev posledic si oglejte naslednje primere:
1. SAT (problem zadovoljivosti):
SAT je dobro znan NP-popoln problem. Če bi bilo NP enako EXPTIME, bi to pomenilo, da je SAT mogoče rešiti v determinističnem eksponentnem času. Še pomembneje, to bi pomenilo, da je SAT mogoče preveriti v polinomskem času in tako rešiti v polinomskem času, kar vodi do (besedilo{P} = besedilo{NP}).
2. Šah:
Znano je, da je problem ugotavljanja, ali ima igralec zmagovalno strategijo v dani šahovski poziciji, v EXPTIME. Če bi bilo NP enako EXPTIME, bi to pomenilo, da je takšen problem mogoče preveriti v polinomskem času, kar trenutno ni mogoče.
zaključek
Vprašanje, ali je lahko razred NP enak razredu EXPTIME, je pomembno v teoriji računalniške kompleksnosti. Na podlagi trenutnega znanja se domneva, da je NP strogo vključen v EXPTIME. Posledice, če bi bil NP enak EXPTIME, bi bile globoke, kar bi povzročilo propad več razredov kompleksnosti in postavilo izziv našemu trenutnemu razumevanju polinomskega v primerjavi z eksponentnim časom.
Druga nedavna vprašanja in odgovori v zvezi kompleksnost:
- Ali razred PSPACE ni enak razredu EXPSPACE?
- Ali je razred kompleksnosti P podmnožica razreda PSPACE?
- Ali lahko dokažemo, da sta razreda Np in P enaka, tako da najdemo učinkovito polinomsko rešitev za kateri koli popolni problem NP na determinističnem TM?
- Ali obstajajo težave v PSPACE, za katere ni znanega algoritma NP?
- Ali je lahko problem SAT popoln problem NP?
- Ali je lahko problem v kompleksnem razredu NP, če obstaja nedeterministični turingov stroj, ki ga bo rešil v polinomskem času
- NP je razred jezikov, ki imajo polinomske časovne verifikatorje
- Ali sta P in NP dejansko enaka zahtevnostna razreda?
- Ali je vsak kontekstno prost jezik v kompleksnem razredu P?
- Ali obstaja protislovje med definicijo NP kot razreda odločitvenih problemov s polinomskimi časovnimi preveritelji in dejstvom, da imajo problemi v razredu P tudi polinomske časovne preveritelje?
Oglejte si več vprašanj in odgovorov v Complexity