Računska teorija složenosti
Kao grana teorije računanja u računarstvu, računska teorija složenosti opisuje skalabilnost algoritama, te inherentnu teškoću u pružanju skalabilnih algoritama za specifične računske probleme. To jest, teorija odgovara na pitanje, "Kako se veličina ulaza algoritma povećava, kako se mijenjaju vrijeme izvršavanja i memorijski zahtjevi algoritma?". Teorija određuje praktične granice na ono što računala mogu obaviti.
Implikacije teorije su važne vladi i industriji. Brzina i memorijski kapacitet računala uvijek rastu, baš kao i veličine skupova podatka koje treba analizirati. Ako algoritam ne uspije skalirati, tada će velika poboljšanja u računarskoj tehnologiji rezultirati tek u marginalnim povećanjima u praktičnim skupovima podataka.
Algoritmi i problemi su kategorizirani u klase složenosti. Najvažnije otvoreno pitanje teorije složenosti jest pitanje istovjetnosti klase P i klase NP, odnosno je li prva podskup druge kao što se općenito smatra. Daleko od toga da se radi o ezoteričnoj vježbi - ubrzo nakon što je pitanje prvi put postavljeno, shvatilo se da su mnogi važni industrijski problemi u polju operacijskih istraživanja potklasa od NP zvana NP-potpuni problemi. NP-potpuni problemi imaju svojstvo da im se rješenja mogu brzo provjeriti, s tim da trenutne metode pronalaženja problema nisu skalabilne. Ako je klasa NP veća od P, tada ne postoji nijedno skalabilno rješenje za ove probleme. Je li to uistinu tako, je jedno od važnih otvorenih pitanja u računskoj teoriji složenosti.
Teorija se složenosti bavi relativnom računskom teškoćom izračunljivih funkcija. Ovo se razlikuje od teorije izračunljivosti, koja se bavi općenitim pitanjem može li se problem riješiti, bez obzira na zahtijevane resurse.
Jedan "problem" je jedinstven skup povezanih pitanja, pri čemu je svako pitanje string konačne duljine. Na primjer, problem FAKTORIZIRAJ jest: za dani cijeli broj zapisan u binarnom sustavu, vrati sve proste faktore tog broja. Pojedinačno se pitanje zove instancom. Na primjer, "daj faktore broja 15" je instanca problema FAKTORIZIRAJ.
Vremenska složenost problema je broj koraka potreban da bi se instanca problema riješila kao funkcija veličine ulaza (obično mjerenog u bitovima) koristeći najučinkovitiji algoritam. Da bi se ovo intuitivno razumjelo, može se razmotriti primjer instance duljine n bitova koja može biti riješena u n² koraka. U ovom primjeru kažemo da je problem vremenske složenosti n². Naravno, točan će broj koraka ovisiti o korištenom stroju. Kako bi se izbjegao taj problem, koristi se veliko O notacija. Ako problem ima vremensku složenost O(n²) na jednom tipičnom računalu, tada će također imati složenost O(n²) na većini drugih računala, tako da nam ova notacija omogućava poopćavanje detalja pojedinačnog računala.
Primjer: Košenje trave ima linearnu vremensku složenost s obzirom na to da treba dvostruko više vremena kako bi se kosilo dvostruko veće područje. Međutim, binarno pretraživanje rječnika ima svega logaritamsku vremensku složenost jer dvostruko veći rječnik treba biti otvoren tek jedan put više (npr. točno u sredini - tada se veličina problema smanji za pola).
Prostorna složenost problema je povezan koncept, koji mjeri količinu prostora, ili memorije koju algoritam zahtijeva. Neformalna bi analogija bila količina papira korištenog za skiciranje prilikom rješavanja problema olovkom i papirom. Prostorna se složenost također mjeri velikom O notacijom.
Različita mjera složenosti problema, korisna u nekim slučajevima, jest složenost sklopa. Ovo je mjera veličine bulovskog sklopa potrebnog za računanje rješenja problema, u terminima broja logičkih vrata zahtijevanih za izgradnju sklopa. Takva je mjera korisna, na primjer, prilikom izgradnje sklopovskih mikročipova za izračunavanje funkcije, radije nego programske podrške.
Veći se dio teorije složenosti bavi problemima odluke. Problem odluke je problem koji uvijek ima odgovor da ili ne. Teorija složenosti razlikuje probleme koji verificiraju odgovore da i one koji verificiraju odgovore ne. Problem koji invertira da i ne odgovore drugog problema se zove komplement tog problema.
Na primjer, poznati problem odluke IS-PRIME vraća odgovor da kad je dani ulaz prost, a inače ne odgovor, dok problem IS-COMPOSITE određuje nije li dani cijeli broj prost broj (tj. složen broj). Kad IS-PRIME vrati da, IS-COMPOSITE vraća ne i obrnuto. Stoga je IS-COMPOSITE komplement problema IS-PRIME, baš kao što je i IS-PRIME komplement problema IS-COMPOSITE.
Problemi se odluke često razmatraju jer proizvoljan problem može uvijek biti sveden na problem odluke. Na primjer, problem HAS-FACTOR jest: za dane cijele brojeve n i k napisane u binarnom sustavu, vrati ima li n neke proste faktore manje od k. Ako problem HAS-FACTOR možemo riješiti korištenjem određene količine resursa, tada možemo to rješenje iskoristiti za rješavanje problema FACTORIZE bez mnogo dodatnih resursa. Ovo se može ostvariti binarnim pretraživanjem na k sve dok nije pronađen najmanji faktor od n, te potom dijeleći tim faktorom i opetujući postupak sve dok svi prosti faktori nisu nađeni.
Važan rezultat teorije složenosti jest činjenica da bez obzira koliko težak problem može postati (tj. koliko vremenskih i prostornih resursa zahtijeva), uvijek će postojati teži problemi. Za vremensku složenost, ovo se dokazuje teoremom o vremenskoj hijerarhiji. Na sličan način može biti izveden teorem o prostornoj hijerarhiji.
Teorija složenosti analizira teškoću računskih problema u terminima mnogo različitih računskih resursa. Isti se problem može opisati u terminima potrebnih količina raznih računskih resursa, uključujući vrijeme, prostor, slučajnost, alternaciju i ostale nešto manje intuitivne mjere. Klasa složenosti je skup svih računskih problema koji mogu biti riješeni koristeći određenu količinu određenog računskog resursa.
Jedni od najviše proučavanih računskih resursa su determinističko vrijeme (DTIME) i deterministički prostor (DSPACE). Ovi resursi predstavljaju količinu vremena računanja i memorijskog prostora potrebnih determinističkom računalu, poput onih stvarno postojećih. Ovi su resursi od velikog praktičnog interesa, i naširoko proučavani.
Neke je računske probleme lakše analizirati u terminima neobičnijih resursa. Na primjer, nedeterministički Turingov stroj je računski model kojem je dozvoljeno grananje kako bi odjednom ispitao mnogo različitih mogućnosti. Nedeterministički Turingov stroj nema mnogo veze sa stvarim fizičkim načinom na koji želimo izračunavati algoritme, ali njegovo grananje točno odgovara mnogim matematičkim modelima koje želimo analizirati, tako da je nedeterminističko vrijeme vrlo važan resurs u analiziranju računskih problema.
Mnogi, još neobičniji računski modeli se koriste u teoriji složenosti. Tehnički, bilo koja se mjera složenosti može shvatiti kao računski resurs, i mjere su složenosti vrlo široko definirane Blumovim aksiomima složenosti.
Klasa složenosti je skup svih računskih problema koji se mogu riješiti koristeći određenu količinu određenog računskog resursa.
Klasa složenosti P je skup svih problema odluke koji mogu biti riješeni determinističkim Turingovim strojem u polinomnom vremenu. Ova klasa odgovara intuitivnoj ideji problema koji mogu biti učinkovito riješeni u najgorim slučajevima.[1]
Klasa složenosti NP je skup problema odluke koji mogu biti riješeni nedeterminističkim Turingovim strojem u polinomnom vremenu. Ova klasa sadrži mnoge probleme koje bi ljudi željeli učinkovito riješiti, uključujući problem bulovske ispunjivosti, problem hamiltonovskog puta i problem prekrivanja vrhova. Svi problemi u ovoj klasi imaju svojstvo da im se rješenja mogu učinkovito provjeriti.[1]
Mnoge se klase složenosti mogu karakterizirati u terminima matemtičke logike potrebnih da bi se izrazili - ovo se polje zove deskriptivna složenost.
Pitanje istovjetnosti skupova NP i P (tj. mogu li problemi koji mogu biti riješeni u nedeterminističkom polinomnom vremenu riješeni u determinističkom polinomnom vremenu) je jedno od najvažnijih otvorenih pitanja u teoretskom računarstvu, s obzirom na široke implikacije koje bi rješenje tog pitanja imalo.[1] Jedna negativna posljedica je ta da bi se mnogi oblici kriptografije mogli jednostavno "razbiti" i stoga postali beskorisni. Međutim, postojale bi i ogromne pozitivne posljedice, jer bi mnogi važni problemi imali učinkovita rješenja. Takvi problemi uključuju razne tipove cjelobrojnog programiranja u operacijskim istraživanjima, mnoge probleme u logistici, predviđanju strukture bjelančevina u biologiji, te sposobnosti učinkovitog pronalaženja formalnih dokaza teorema u čistoj matematici korištenjem računala.[2][3] Clay Mathematics Institute je 2000. obavio da će isplatiti nagradu od USD$ 1 000 000 prvoj osobi koja dokaže rješenje.[4]
Pitanja poput ovih motiviraju koncepte težine i potpunosti. Skup problema X je težak za skup problema Y ako svaki problem u Y može "lako" biti transformiran u neki problem u X koji producira rješenje. Definicija "lakog" je različita u različitim kontekstima. Važan teški skup u teoriji složenosti jest NP-težak - skup problema koji nisu nužno sami u NP, ali na koje bilo koji NP problem može biti sveden u polinomnom vremenu.
Skup X je potpun za Y ako je težak za Y, ali je također i podskup od Y. Važan potpun skup u teoriji složenosti je NP-potpun skup. Ovaj skup sadrži "najteže" probleme u NP, u smislu da su to oni koji najizglednije nisu u P. Zbog činjenice da problem P = NP ostaje neriješen, svođenje bi problema na poznati NP-potpun problem indiciralo da ne postoji poznato vremenski polinomno rješenje za njega. Slično, jer svi NP problemi mogu biti svedeni na skup, pronalaženje NP-potpunog problema koji bi mogao biti riješen u polinomnom vremenu bi značilo P = NP.[1]
Drugo otvoreno pitanje vezano za problem P = NP jest postoje li problemi koji su u NP, ali ne i u P, koji nisu NP-potpuni. Drugim riječima, problemi koji trebaju biti riješeni u nedeterminističkom polinomnom vremenu, ali ne mogu biti svedeni na polinomno vrijeme iz drugih nedeterminističkih vremenski polinomnih problema. Jedan takav problem, za koji se zna da je NP ali ne i da je NP-potpun, jest problem izomorfizma grafa - problem koji pokušava odlučiti jesu li dva grafa izomorfna (tj. dijele li ista svojstva, v. izomorfni graf). Pokazano je da ako vrijedi P ≠ NP, da takvi problemi postoje.[6]
Gdje je co-NP skup koji sadrži komplementarne probleme (tj. problem s invertiranim da/ne odgovorima) NP problema. Vjeruje se da te dvije klase nisu jednake, iako to dosad nije dokazano. Pokazano je da ako ove dvije klase nisu jednake, da tada slijedi da nijedan NP-potpun problem ne može biti u co-NP i nijedan co-NP-potpun problem ne može biti u NP.[6]
Problemi koji su rješivi u teoriji, ali ne mogu biti riješeni u praksi, se zovu neukrotivima (engl. intractable). Što točno može biti riješeno "u praksi" je otvoreno za diskusiju, ali općenito su samo problemi koji imaju vremenski polinomna rješenja rješivi za više od najmanjih ulaza. Problemi za koje se zna da su neukrotivi uključuju one koji su EXPTIME-potpuni. Ako NP nije isti kao i P, tada su NP-potpuni problemi također neukrotivi.
Da bi se vidjelo zašto rješenja u eksponencijalnom vremenu nisu uporabljiva u praksi, neka se razmotri problem koji zahtijeva 2n operacija za rješavanje (n je veličina ulaza). Za relativno male ulaze od n=100, i pretpostavljajući računalo koje može obaviti 1012 operacija u sekundi, rješenje bi zahtijevalo 4*1010 godina, mnogo više od trenutne starosti svemira.
- Laszlo Babai
- Manuel Blum, koji je razvio aksiomatsku teoriju složenosti zasnovanu na Blumovim aksiomima
- Allan Borodin
- Stephen Cook
- Uriel Feige
- Michael R. Garey
- Oded Goldreich
- Juris Hartmanis
- Johan Håstad
- Russell Impagliazzo
- David S. Johnson
- Richard Karp
- Marek Karpinski
- Leonid Levin
- Jack Lutz
- Christos H. Papadimitriou
- Alexander Razborov
- Steven Rudich
- Walter Savitch
- Adi Shamir
- Michael Sipser
- Richard Stearns
- Madhu Sudan
- Leslie Valiant
- Andrew Yao
- L. Fortnow, Steve Homer (2002./2003.). Kratka povijest računske složenosti. In D. van Dalen, J. Dawson, and A. Kanamori, urednici, The History of Mathematical Logic. North-Holland, Amsterdam.
- Jan van Leeuwen, ur. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, The MIT Press/Elsevier, 1990. ISBN 978-0-444-88071-0 (Volume A). QA 76.H279 1990. Ogroman kompendij informacije, tisuće regerenci u različitim člancima.
- ↑ a b c d
Sipser, Michael. 2006. Time Complexity. Introduction to the Theory of Computation. 2nd edition izdanje. Thomson Course Technology. USA. ISBN 0534950973
|edition=sadrži dodatni tekst (pomoć) - ↑
Berger, Bonnie A.; Leighton, Terrance. 1998. Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete. Journal of Computational Biology. 5 (1): p27-40. PMID 9541869
|pages=sadrži dodatni tekst (pomoć) - ↑ Cook, Stephen. Travanj 2000. The P versus NP Problem (PDF). Clay Mathematics Institute. Inačica izvorne stranice (PDF) arhivirana 12. prosinca 2010. Pristupljeno 30. travnja 2007. journal zahtijeva
|journal=(pomoć) - ↑ Jaffe, Arthur M. The Millennium Grand Challenge in Mathematics (PDF). Notices of the AMS. 53 (6). Pristupljeno 18. listopada 2006.
- ↑ Ladner, Richard E. 1975. On the structure of polynomial time reducibility (PDF). Journal of the ACM (JACM). 22 (1): 151–171. doi:10.1145/321864.321877
- ↑ a b
Du, Ding-Zhu; Ko, Ker-I. 2000. Theory of Computational Complexity. John Wiley & Sons. ISBN 978-0-471-34506-0 Nepoznati parametar
|country=zanemaren (pomoć)
- The Complexity Zoo Arhivirana inačica izvorne stranice od 28. studenoga 2006. (Wayback Machine) - wiki o klasama složenosti
- Besplatna knjiga o računskoj složenosti