Теорија комплексности

Грана теорије израчунљивости у рачунарству, рачунарска теорија комплексности описује скалабилност алгоритама, и инхерентну тешкоћу у изналажењу скалабилних алгоритама за специфичне рачунарске проблеме. Другим речима, теорија комплексности одговара на питање Када се величина улаза за алгоритам повећава, како се мењају време извршавања и меморијски захтеви, и које су импликације и тих промена? Ова теорија одређује практичне границе онога шта рачунари могу да постигну.

Резултати теорије комплексности су од значаја и за науку и за привреду. Брзина и меморијски капацитет рачунара се стално повећавају, али се повећава и количина података која се анализира. Ако алгоритми нису скалабилни, тада чак и јако велика унапређења у рачунарској технологији понекад могу да доведу само до незнатних повећања количине података која може да се анализира.

Алгоритми и проблеми су категоризовани у класе комплексности. Најважније отворено питање у теорији комплексности је да ли је класа П иста као класа НП, или јој је само подскуп, као што је опште уверење. Ово није само суво теоријско разматрање, јер убрзо након што је ово питање први пут постављено, откривено је да су многи важни индустријски проблеми из подкласе класе НП, коју називамо класа НП-комплетних проблема. НП-комплетни проблеми имају својство да се њихова решења могу брзо проверити, али тренутно постојећи методи за налажење тачних решења нису скалабилни. Ако је класа НП једнака класи П, онда постоји скалабилно решење за све проблеме из класе НП. Ово међутим још увек није утврђено, и једно је од најважнијих отворених питања у рачунарству данас.

Преглед

Теорија се сложености бави релативном рачунском тешкоћом израчунљивих функција. Ово се разликује од теорије израчунљивости, која се бави генералним питањем може ли се проблем решити, без обзира на захтеване ресурсе.

Један „проблем” је јединствен скуп повезаних питања, при чему је свако питање стринг коначне дужине. На пример, проблем ФАКТОРИЗИРАЈ јесте: за дати цели број записан у бинарном систему, врати све просте факторе тог броја. Појединачно се питање зове инстанцом. На пример, „дај факторе броја 15” је инстанца проблема ФАКТОРИЗИРАЈ.

Временска сложеност проблема је број корака потребан да би се инстанца проблема решила као функција величине улаза (обично мереног у битовима) користећи најефектнији алгоритам. Да би се ово интуитивно разумело, може се размотрити пример инстанце дужине n битова која може бити решена у n² корака. У овом примеру каже се да је проблем временске сложености n². Наравно, тачан ће број корака зависи од кориштеног приступа. Како би се избегао тај проблем, користи се велико О нотација. Ако проблем има временску сложеност O(n²) на једном типичном рачунару, тада ће такође имати сложеност O(n²) на већини других рачунара, тако да ова нотација омогућава поопштавање детаља појединачног рачунара.

Пример: Кошење траве има линеарну временску сложеност с обзиром да треба двоструко више времена како би се косило двоструко веће подручје. Међутим, бинарно претраживање речника има свега логаритамску временску сложеност будући да двоструко већи речник треба бити отворен тек један пут више (нпр. тачно у средини - тада се величина проблема смањи за пола).

Просторна сложеност проблема је повезан концепт, који мери количину простора, или меморије коју алгоритам захтева. Неформална би аналогија била количина папира кориштеног за скицирање приликом решавања проблема оловком и папиром. Просторна се сложеност такође мери великом О нотацијом.

Различита мера сложености проблема, корисна у неким случајевима, јест сложеност склопа. Ово је мера величине буловског склопа потребног за рачунање решења проблема, у терминима броја логичких врата захтеваних за изградњу склопа. Таква је мера корисна, на пример, приликом изградње склоповских микрочипова за израчунавање функције, радије него програмске подршке.

Класе сложености

Класа сложености је скуп свих рачунских проблема који се могу решити користећи одређену количину одређеног рачунског ресурса.

Класа сложености P је скуп свих проблема одлуке који могу бити решени детерминистичком Тјуринговим машином у полиномном времену. Ова класа одговара интуитивној идеји проблема који могу бити делотворно решени у најгорим случајевима.

Класа сложености НП је скуп проблема одлуке који могу бити решени недетерминистичком Тјуринговом машином у полиномном времену. Ова класа садржи многе проблеме које би људи желели делотворно да реше, укључујући проблем буловске испуњивости, проблем хамилтоновског пута и проблем прекривања врхова. Сви проблеми у овој класи имају својство да им се решења могу делотворно проверити.

Многе се класе сложености могу карактеризирати у терминима математичке логике потребних да би се изразили - ово се поље зове дескриптивна сложеност.

Отворена питања

P = NP питање

Види још: [[:Класе сложености P и NP]]

Питање истоветности скупова NP и P (тј. могу ли проблеми који могу бити решени у недетерминистичком полиномном времену, решени у детерминистичком полиномном времену) је једно од најважнијих отворених питања у теоретском рачунарству, с обзиром на широке импликације које би решење тог питања имало. Једна негативна последица је та да би се многи облици криптографије могли једноставно „разбити” и стога постали бескорисни. Међутим, постојале би и огромне позитивне последице, будући да би многи важни проблеми имали ефикасна решења. Такви проблеми укључују разне типове целобројног програмирања у операцијским истраживањима, многе проблеме у логистици, предвиђању структуре беланчевина у биологији, те способности делотворног проналажења формалних доказа теорема у чистој математици кориштењем рачунара. Клејов математички институт је 2000. обавио да ће исплатити награду од УСД$ 1 000 000 првој особи која докаже решење.

Питања попут ових мотивирају концепте тежине и потпуности. Скуп проблема X је тежак за скуп проблема Y ако сваки проблем у Y може "лако" бити трансформиран у неки проблем у X који производи решење. Дефиниција „лаког” је различита у различитим контекстима. Важан тешки скуп у теорији сложености јесте NP-тежак - скуп проблема који нису нужно сами у NP, али на које било који NP проблем може бити сведен у полиномном времену.

Скуп X је потпун за Y ако је тежак за Y, али је такође и подскуп од Y. Важан потпун скуп у теорији сложености је NP-потпун скуп. Овај скуп садржи „најтеже” проблеме у NP, у смислу да су то они који најизгледније нису у P. Због чињенице да проблем P = NP остаје нерешен, свођење би проблема на познати NP-потпун проблем индицирало да не постоји познато временски полиномно решење за њега. Слично, будући да сви NP проблеми могу бити сведени на скуп, проналажење NP-потпуног проблема који би могао бити решен у полиномном времену би значило P = NP.

Непотпуни проблеми у NP

Дијаграм класа сложености уз претпоставку да вреди P ≠ NP. Постојање проблема изван класа и P и NP-потпун у овом случају је поставио Ладнер.

Друго отворено питање везано за проблем P = NP јесте постоје ли проблеми који су у NP, али не и у P, који нису NP-потпуни. Другим речима, проблеми који требају бити решени у недетерминистичком полиномном времену, али не могу бити сведени на полиномно време из других недетерминистичких временски полиномних проблема. Један такав проблем, за који се зна да је NP али не и да је NP-потпун, јест проблем изоморфизма графа - проблем који покушава одлучити јесу ли два графа изоморфна (тј. деле ли иста својства). Показано је да ако вреди P ≠ NP, да такви проблеми постоје.

NP = ко-NP

Где је ко-NP скуп који садржи комплементарне проблеме (тј. проблем са инвертираним да/не одговорима) NP проблема. Верује се да те две класе нису једнаке, иако то досад није доказано. Показано је да ако ове две класе нису једнаке, да тада следи да недан NP-потпун проблем не може бити у ко-NP, и ниједан ко-NP-потпун проблем не може бити у NP.

Види још

• Мастер теорема

Литература

• 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, ур. (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 изд.), Addison Wesley, ISBN 978-0-201-53082-7 
• Sipser, Michael (2006), Introduction to the Theory of Computation (2nd изд.), 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, Архивирано из оригинала (PDF) 22. 7. 2018. г., Приступљено 24. 10. 2017 CS1 одржавање: Формат датума (веза)
• 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., ур. (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 (објављено 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 (објављено 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 изд.). Cambridge UK: Cambridge University Press. ISBN 0-521-20402-X. 
• Boolos, George; Burgess, John; Jeffrey, Richard (2002). Computability and Logic (4th изд.). 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 изд.). 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 изд.). 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 изд.). 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 изд.). 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 изд.). 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 изд.). 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.

Спољашње везе

• 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