Teorija kompleksnosti

Grana teorije izračunljivosti u računarstvu, računarska teorija kompleksnosti opisuje skalabilnost algoritama, i inherentnu teškoću u iznalaženju skalabilnih algoritama za specifične računarske probleme. Drugim rečima, teorija kompleksnosti odgovara na pitanje Kada se veličina ulaza za algoritam povećava, kako se menjaju vreme izvršavanja i memorijski zahtevi, i koje su implikacije i tih promena? Ova teorija određuje praktične granice onoga šta računari mogu da postignu.

Rezultati teorije kompleksnosti su od značaja i za nauku i za privredu. Brzina i memorijski kapacitet računara se stalno povećavaju, ali se povećava i količina podataka koja se analizira. Ako algoritmi nisu skalabilni, tada čak i jako velika unapređenja u računarskoj tehnologiji ponekad mogu da dovedu samo do neznatnih povećanja količine podataka koja može da se analizira.

Algoritmi i problemi su kategorizovani u klase kompleksnosti. Najvažnije otvoreno pitanje u teoriji kompleksnosti je da li je klasa P ista kao klasa NP, ili joj je samo podskup, kao što je opšte uverenje. Ovo nije samo suvo teorijsko razmatranje, jer ubrzo nakon što je ovo pitanje prvi put postavljeno, otkriveno je da su mnogi važni industrijski problemi iz podklase klase NP, koju nazivamo klasa NP-kompletnih problema. NP-kompletni problemi imaju svojstvo da se njihova rešenja mogu brzo proveriti, ali trenutno postojeći metodi za nalaženje tačnih rešenja nisu skalabilni. Ako je klasa NP jednaka klasi P, onda postoji skalabilno rešenje za sve probleme iz klase NP. Ovo međutim još uvek nije utvrđeno, i jedno je od najvažnijih otvorenih pitanja u računarstvu danas.

Pregled

Teorija se složenosti bavi relativnom računskom teškoćom izračunljivih funkcija. Ovo se razlikuje od teorije izračunljivosti, koja se bavi generalnim pitanjem može li se problem rešiti, bez obzira na zahtevane resurse.

Jedan „problem” je jedinstven skup povezanih pitanja, pri čemu je svako pitanje string konačne dužine. Na primer, problem FAKTORIZIRAJ jeste: za dati celi broj zapisan u binarnom sistemu, vrati sve proste faktore tog broja. Pojedinačno se pitanje zove instancom. Na primer, „daj faktore broja 15” je instanca problema FAKTORIZIRAJ.

Vremenska složenost problema je broj koraka potreban da bi se instanca problema rešila kao funkcija veličine ulaza (obično merenog u bitovima) koristeći najefektniji algoritam. Da bi se ovo intuitivno razumelo, može se razmotriti primer instance dužine n bitova koja može biti rešena u n² koraka. U ovom primeru kaže se da je problem vremenske složenosti n². Naravno, tačan će broj koraka zavisi od korištenog pristupa. Kako bi se izbegao taj problem, koristi se veliko O notacija. Ako problem ima vremensku složenost O(n²) na jednom tipičnom računaru, tada će takođe imati složenost O(n²) na većini drugih računara, tako da ova notacija omogućava poopštavanje detalja pojedinačnog računara.

Primer: Košenje trave ima linearnu vremensku složenost s obzirom da treba dvostruko više vremena kako bi se kosilo dvostruko veće područje. Međutim, binarno pretraživanje rečnika ima svega logaritamsku vremensku složenost budući da dvostruko veći rečnik treba biti otvoren tek jedan put više (npr. tačno u sredini - tada se veličina problema smanji za pola).

Prostorna složenost problema je povezan koncept, koji meri količinu prostora, ili memorije koju algoritam zahteva. Neformalna bi analogija bila količina papira korištenog za skiciranje prilikom rešavanja problema olovkom i papirom. Prostorna se složenost takođe meri velikom O notacijom.

Različita mera složenosti problema, korisna u nekim slučajevima, jest složenost sklopa. Ovo je mera veličine bulovskog sklopa potrebnog za računanje rešenja problema, u terminima broja logičkih vrata zahtevanih za izgradnju sklopa. Takva je mera korisna, na primer, prilikom izgradnje sklopovskih mikročipova za izračunavanje funkcije, radije nego programske podrške.

Klase složenosti

Klasa složenosti je skup svih računskih problema koji se mogu rešiti koristeći određenu količinu određenog računskog resursa.

Klasa složenosti P je skup svih problema odluke koji mogu biti rešeni determinističkom Tjuringovim mašinom u polinomnom vremenu. Ova klasa odgovara intuitivnoj ideji problema koji mogu biti delotvorno rešeni u najgorim slučajevima.

Klasa složenosti НП je skup problema odluke koji mogu biti rešeni nedeterminističkom Tjuringovom mašinom u polinomnom vremenu. Ova klasa sadrži mnoge probleme koje bi ljudi želeli delotvorno da reše, uključujući problem bulovske ispunjivosti, problem hamiltonovskog puta i problem prekrivanja vrhova. Svi problemi u ovoj klasi imaju svojstvo da im se rešenja mogu delotvorno proveriti.

Mnoge se klase složenosti mogu karakterizirati u terminima matematičke logike potrebnih da bi se izrazili - ovo se polje zove deskriptivna složenost.

Otvorena pitanja

P = NP pitanje

Vidi još: [[:Klase složenosti P i NP]]

Pitanje istovetnosti skupova NP i P (tj. mogu li problemi koji mogu biti rešeni u nedeterminističkom polinomnom vremenu, rešeni u determinističkom polinomnom vremenu) je jedno od najvažnijih otvorenih pitanja u teoretskom računarstvu, s obzirom na široke implikacije koje bi rešenje tog pitanja imalo. Jedna negativna posledica je ta da bi se mnogi oblici kriptografije mogli jednostavno „razbiti” i stoga postali beskorisni. Međutim, postojale bi i ogromne pozitivne posledice, budući da bi mnogi važni problemi imali efikasna rešenja. Takvi problemi uključuju razne tipove celobrojnog programiranja u operacijskim istraživanjima, mnoge probleme u logistici, predviđanju strukture belančevina u biologiji, te sposobnosti delotvornog pronalaženja formalnih dokaza teorema u čistoj matematici korištenjem računara. Klejov matematički institut je 2000. obavio da će isplatiti nagradu od USD$ 1 000 000 prvoj osobi koja dokaže rešenje.

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 proizvodi rešenje. Definicija „lakog” je različita u različitim kontekstima. Važan teški skup u teoriji složenosti jeste 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đe 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 nerešen, svođenje bi problema na poznati NP-potpun problem indiciralo da ne postoji poznato vremenski polinomno rešenje za njega. Slično, budući da svi NP problemi mogu biti svedeni na skup, pronalaženje NP-potpunog problema koji bi mogao biti rešen u polinomnom vremenu bi značilo P = NP.

Nepotpuni problemi u NP

Dijagram klasa složenosti uz pretpostavku da vredi P ≠ NP. Postojanje problema izvan klasa i P i NP-potpun u ovom slučaju je postavio Ladner.

Drugo otvoreno pitanje vezano za problem P = NP jeste postoje li problemi koji su u NP, ali ne i u P, koji nisu NP-potpuni. Drugim rečima, problemi koji trebaju biti rešeni u nedeterminističkom polinomnom vremenu, ali ne mogu biti svedeni na polinomno vreme 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. dele li ista svojstva). Pokazano je da ako vredi P ≠ NP, da takvi problemi postoje.

NP = ko-NP

Gde je ko-NP skup koji sadrži komplementarne probleme (tj. problem sa invertiranim da/ne odgovorima) NP problema. Veruje se da te dve klase nisu jednake, iako to dosad nije dokazano. Pokazano je da ako ove dve klase nisu jednake, da tada sledi da nedan NP-potpun problem ne može biti u ko-NP, i nijedan ko-NP-potpun problem ne može biti u NP.

Vidi još

• Master teorema

Literatura

• Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press, ISBN 978-0-521-42426-4, Zbl 1193.68112 
• Downey, Rod; Fellows, Michael (1999), Parameterized complexity, Monographs in Computer Science, Berlin, New York: Springer-Verlag, ISBN 9780387948836 
• Du, Ding-Zhu; Ko, Ker-I (2000), Theory of Computational Complexity, John Wiley & Sons, ISBN 978-0-471-34506-0 
• Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge University Press 
• van Leeuwen, Jan, ur. (1990), Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, ISBN 978-0-444-88071-0 
• Papadimitriou, Christos (1994), Computational Complexity (1st izd.), Addison Wesley, ISBN 978-0-201-53082-7 
• Sipser, Michael (2006), Introduction to the Theory of Computation (2nd izd.), USA: Thomson Course Technology, ISBN 978-0-534-95097-2 
• Khalil, Hatem; Ulery, Dana (1976), „A Review of Current Studies on Complexity of Algorithms for Partial Differential Equations”, Proceedings of the Annual Conference on - ACM 76, ACM '76: 197—201, ISBN 9781450374897, S2CID 15497394, doi:10.1145/800191.805573 
• Cook, Stephen (1983), „An overview of computational complexity” (PDF), Commun. ACM, 26 (6): 400—408, ISSN 0001-0782, S2CID 14323396, doi:10.1145/358141.358144, Arhivirano iz originala (PDF) 22. 7. 2018. g., Pristupljeno 24. 10. 2017 CS1 održavanje: Format datuma (veza)
• Fortnow, Lance; Homer, Steven (2003), „A Short History of Computational Complexity” (PDF), Bulletin of the EATCS, 80: 95—133 
• Mertens, Stephan (2002), „Computational Complexity for Physicists”, Computing in Science and Eng., 4 (3): 31—47, Bibcode:2002CSE.....4c..31M, ISSN 1521-9615, S2CID 633346, arXiv:cond-mat/0012185 , doi:10.1109/5992.998639 
• Wuppuluri, Shyam; Doria, Francisco A., ur. (2020), Unravelling Complexity: The Life and Work of Gregory Chaitin, World Scientific, ISBN 978-981-12-0006-9, S2CID 198790362, doi:10.1142/11270 
• B. Jack Copeland ed. (2004), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Clarendon Press (Oxford University Press), Oxford UK, ISBN 0-19-825079-7. Contains the Turing papers plus a draft letter to Emil Post re his criticism of "Turing's convention", and Donald W. Davies' Corrections to Turing's Universal Computing Machine
• Martin Davis (ed.) (1965), The Undecidable, Raven Press, Hewlett, NY.
• Emil Post (1936), "Finite Combinatory Processes—Formulation 1", Journal of Symbolic Logic, 1, 103–105, 1936. Reprinted in The Undecidable, pp. 289ff.
• Emil Post (1947), "Recursive Unsolvability of a Problem of Thue", Journal of Symbolic Logic, vol. 12, pp. 1–11. Reprinted in The Undecidable, pp. 293ff. In the Appendix of this paper Post comments on and gives corrections to Turing's paper of 1936–1937. In particular see the footnotes 11 with corrections to the universal computing machine coding and footnote 14 with comments on Turing's first and second proofs.
• Turing, A.M. (1936). „On Computable Numbers, with an Application to the Entscheidungsproblem”. Proceedings of the London Mathematical Society. 2 (objavljeno 1937). 42: 230—265. doi:10.1112/plms/s2-42.1.230.  (and Turing, A.M. (1938). „On Computable Numbers, with an Application to the Entscheidungsproblem: A correction”. Proceedings of the London Mathematical Society. 2 (objavljeno 1937). 43 (6): 544—6. doi:10.1112/plms/s2-43.6.544. ). Reprinted in many collections, e.g. in The Undecidable, pp. 115–154; available on the web in many places.
• Alan Turing, 1948, "Intelligent Machinery." Reprinted in "Cybernetics: Key Papers." Ed. C.R. Evans and A.D.J. Robertson. Baltimore: University Park Press, 1968. p. 31. Reprinted in Turing, A. M. (1996). „Intelligent Machinery, A Heretical Theory”. Philosophia Mathematica. 4 (3): 256—260. doi:10.1093/philmat/4.3.256. 
• F. C. Hennie and R. E. Stearns. Two-tape simulation of multitape Turing machines. JACM, . 13 (4): 533—546.  , 1966.
• Boolos, George; Jeffrey, Richard (1999) [1989]. Computability and Logic (3rd izd.). Cambridge UK: Cambridge University Press. ISBN 0-521-20402-X. 
• Boolos, George; Burgess, John; Jeffrey, Richard (2002). Computability and Logic (4th izd.). Cambridge UK: Cambridge University Press. ISBN 0-521-00758-5.  Some parts have been significantly rewritten by Burgess. Presentation of Turing machines in context of Lambek "abacus machines" (cf. Register machine) and recursive functions, showing their equivalence.
• Taylor L. Booth (1967), Sequential Machines and Automata Theory, John Wiley and Sons, Inc., New York. Graduate level engineering text; ranges over a wide variety of topics, Chapter IX Turing Machines includes some recursion theory.
• Davis, Martin (1958). Computability and Unsolvability. McGraw-Hill Book Company, Inc, New York. . On pages 12–20 he gives examples of 5-tuple tables for Addition, The Successor Function, Subtraction (x ≥ y), Proper Subtraction (0 if x < y), The Identity Function and various identity functions, and Multiplication.
• Davis, Martin; Sigal, Ron; Elaine J. Weyuker (1994). Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science (2nd izd.). San Diego: Academic Press, Harcourt, Brace & Company. ISBN 0-12-206382-1. 
• Hennie, Fredrick (1977). Introduction to Computability. Addison–Wesley, Reading, Mass. QA248.5H4 1977. . On pages 90–103 Hennie discusses the UTM with examples and flow-charts, but no actual 'code'.
• Hopcroft, John; Jeffrey Ullman (1979). Introduction to Automata Theory, Languages, and Computation (1st izd.). Addison–Wesley, Reading Mass. ISBN 0-201-02988-X.  Centered around the issues of machine-interpretation of "languages", NP-completeness, etc.
• Hopcroft, John E.; Motwani, Rajeev; Jeffrey D. Ullman (2001). Introduction to Automata Theory, Languages, and Computation (2nd izd.). Reading Mass: Addison–Wesley. ISBN 0-201-44124-1.  Distinctly different and less intimidating than the first edition.
• Stephen Kleene (1952), Introduction to Metamathematics, North–Holland Publishing Company, Amsterdam Netherlands, 10th impression (with corrections of 6th reprint 1971). Graduate level text; most of Chapter XIII Computable functions is on Turing machine proofs of computability of recursive functions, etc.
• Knuth, Donald E. (1973). Volume 1/Fundamental Algorithms: The Art of computer Programming (2nd izd.). Reading, Mass.: Addison–Wesley Publishing Company. . With reference to the role of Turing machines in the development of computation (both hardware and software) see 1.4.5 History and Bibliography pp. 225ff and 2.6 History and Bibliographypp. 456ff.
• Zohar Manna, 1974, Mathematical Theory of Computation. Reprinted, Dover, ISBN 978-0-486-43238-0.
• Marvin Minsky, Computation: Finite and Infinite Machines, Prentice–Hall, Inc., N.J., 1967. See Chapter 8, Section 8.2 "Unsolvability of the Halting Problem." Excellent, i.e. relatively readable, sometimes funny.
• Papadimitriou, Christos (1993). Computational Complexity (1st izd.). Addison Wesley. ISBN 0-201-53082-1.  Chapter 2: Turing machines, pp. 19–56.
• Hartley Rogers, Jr., Theory of Recursive Functions and Effective Computability, The MIT Press, Cambridge MA, paperback edition 1987, original McGraw-Hill edition (1967) ISBN 0-262-68052-1 (pbk.)
• Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Chapter 3: The Church–Turing Thesis, pp. 125–149.
• Stone, Harold S. (1972). Introduction to Computer Organization and Data Structures (1st izd.). New York: McGraw–Hill Book Company. ISBN 0-07-061726-0. 
• Peter van Emde Boas 1990, Machine Models and Simulations, pp. 3–66, in Jan van Leeuwen, ed., Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, The MIT Press/Elsevier, [place?], ISBN 0-444-88071-2 (Volume A). QA76.H279 1990.

Spoljašnje veze

• The Complexity Zoo Архивирано на сајту Wayback Machine (27. август 2019)
• Hazewinkel Michiel, ур. (2001). „Computational complexity classes”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104. 
• What are the most important results (and papers) in complexity theory that every one should know?
• Scott Aaronson: Why Philosophers Should Care About Computational Complexity