Vai problēma var būt NP sarežģītības klasē, ja ir nedeterministiska tūringa mašīna, kas to atrisinās polinoma laikā
Jautājums "Vai problēma var būt NP sarežģītības klasē, ja ir nedeterministiska Tjūringa mašīna, kas to atrisinās polinoma laikā?" skar skaitļošanas sarežģītības teorijas pamatjēdzienus. Lai visaptveroši risinātu šo jautājumu, mums jāapsver NP sarežģītības klases definīcijas un raksturlielumi un nedeterministisko Tjūringa mašīnu (NDTM) loma.
NP definīcija
Klase NP (nondeterministic polynomial time) sastāv no lēmumu problēmām, kurām doto risinājumu var pārbaudīt kā pareizu vai nepareizu polinoma laikā ar deterministisko Tjūringa mašīnu (DTM). Formāli lēmuma problēma ir NP, ja pastāv polinoma laika verifikācijas algoritms, kas var pārbaudīt dotā sertifikāta (vai liecinieka) pareizību problēmas gadījumam.
Nedeterministiskās Tjūringa mašīnas
Nedeterministiska Tjūringa mašīna ir teorētisks skaitļošanas modelis, kas paplašina deterministiskās Tjūringa mašīnas iespējas. Atšķirībā no DTM, kas seko vienam skaitļošanas ceļam, ko nosaka tā pārejas funkcija, NDTM var izmantot vairākus skaitļošanas ceļus vienlaikus. Katrā solī NDTM var "izvēlēties" no iespējamo pāreju kopas, efektīvi pētot daudzus iespējamos aprēķinus paralēli.
Polinoma laika atrisināmība ar NDTM
Tiek uzskatīts, ka problēma ir atrisināma ar NDTM polinoma laikā, ja pastāv nedeterministisks algoritms, kas var atrast problēmas risinājumu vairākos soļos, kas ir polinoma ievades lieluma. Tas nozīmē, ka jebkurā problēmas gadījumā NDTM var izpētīt skaitļošanas ceļu, kas noved pie risinājuma polinoma laikā.
Saistība starp NP un NDTM
Klasi NP var līdzvērtīgi definēt NDTM izteiksmē. Konkrēti, lēmuma problēma ir NP tad un tikai tad, ja pastāv NDTM, kas var atrisināt problēmu polinoma laikā. Šī līdzvērtība izriet no fakta, ka NDTM var uzminēt sertifikātu nedeterministiski un pēc tam to deterministiski pārbaudīt polinoma laikā.
Lai to ilustrētu ar piemēru, apsveriet labi zināmo NP-pilnīgo problēmu, Būla apmierinātības problēmu (SAT). Ņemot vērā Būla formulu konjunktīvā normālā formā (CNF), uzdevums ir noteikt, vai pastāv patiesības vērtību piešķiršana mainīgajiem, kas padara formulu patiesu. NDTM var atrisināt SAT polinoma laikā, nedeterministiski uzminot patiesības vērtību piešķiršanu un pēc tam deterministiski pārbaudot, vai piešķiršana atbilst formulai. Pārbaudes darbību, kas ietver formulas novērtēšanu saskaņā ar uzminēto uzdevumu, var veikt polinoma laikā.
NDTM polinomu laika atrisināmības ietekme
Ņemot vērā iepriekš minētās definīcijas un ekvivalenci starp NP un polinoma laika atrisināmību ar NDTM, mēs varam secināt, ka, ja pastāv NDTM, kas atrisina problēmu polinoma laikā, tad problēma patiešām ir NP. Tas ir tāpēc, ka šāda NDTM esamība nozīmē, ka problēmai ir polinoma laika verifikācijas algoritms. NDTM nedeterministiskā minēšanas fāze atbilst sertifikāta ģenerēšanai, bet deterministiskā verifikācijas fāze atbilst polinoma laika verifikācijas algoritmam.
Papildu apsvērumi un piemēri
Lai sīkāk izskaidrotu šo koncepciju, apskatīsim papildu piemērus par problēmām NP un to saistību ar NDTM:
1. Hamiltona ceļa problēma: Izmantojot grafiku, Hamiltona ceļa uzdevums jautā, vai pastāv ceļš, kas katru virsotni apmeklē tieši vienu reizi. NDTM var atrisināt šo problēmu polinoma laikā, nedeterministiski uzminot virsotņu secību un pēc tam pārbaudot, vai secība veido derīgu Hamiltona ceļu. Pārbaudes darbība ietver secīgu virsotņu blakusesības pārbaudi un katras virsotnes apmeklējuma nodrošināšanu tieši vienreiz, un to abus var izdarīt polinoma laikā.
2. Apakškopas summas problēma: ņemot vērā veselu skaitļu kopu un mērķa summu, apakškopas summas uzdevums jautā, vai pastāv veselu skaitļu apakškopa, kas summējas ar mērķi. NDTM var atrisināt šo problēmu polinoma laikā, nedeterministiski uzminot veselu skaitļu apakškopu un pēc tam pārbaudot, vai apakškopas summa ir vienāda ar mērķi. Pārbaudes darbība ietver uzminētās apakškopas elementu summēšanu, ko var veikt polinoma laikā.
3. Grafiku krāsošanas problēma: ņemot vērā grafiku un vairākas krāsas, Graph Coloring uzdevums jautā, vai ir iespējams krāsot grafika virsotnes tā, lai divām blakus esošajām virsotnēm nebūtu vienādas krāsas. NDTM var atrisināt šo problēmu polinoma laikā, nedeterministiski piešķirot virsotnēm krāsas un pēc tam pārbaudot, vai krāsa ir derīga. Pārbaudes darbība ietver blakus esošo virsotņu krāsu pārbaudi, ko var veikt polinoma laikā.
Secinājumi
Ņemot vērā sniegtās definīcijas un piemērus, ir skaidrs, ka problēma patiešām var būt NP sarežģītības klasē, ja pastāv nedeterministiska Tjūringa mašīna, kas to atrisinās polinoma laikā. Šīs attiecības ir skaitļošanas sarežģītības teorijas stūrakmens un uzsver līdzvērtību starp NDTM atrisināmību polinoma laikā un dalību NP klasē.
Citi jaunākie jautājumi un atbildes par sarežģītība:
- Vai PSPACE klase nav vienāda ar EXPSPACE klasi?
- Vai P sarežģītības klase ir PSPACE klases apakškopa?
- Vai mēs varam pierādīt, ka Np un P klase ir vienādas, atrodot efektīvu polinoma risinājumu jebkurai NP pilnīgai problēmai deterministiskā TM?
- Vai NP klase var būt vienāda ar EXPTIME klasi?
- Vai PSPACE ir problēmas, kurām nav zināms NP algoritms?
- Vai SAT problēma var būt pilnīga NP problēma?
- NP ir valodu klase, kurām ir polinoma laika verificētāji
- Vai P un NP patiesībā ir viena un tā pati sarežģītības klase?
- Vai P sarežģītības klasē katra valoda ir brīva no konteksta?
- Vai pastāv pretruna starp NP definīciju kā lēmumu problēmu klase ar polinoma laika pārbaudītājiem un to, ka P klases uzdevumiem ir arī polinoma laika pārbaudītāji?
Skatiet vairāk jautājumu un atbilžu sadaļā Sarežģītība