Корисник:VikiNikolaKostadinovic/песак

Редукција полиномиалне временске сложености[уреди | уреди извор]

У теорији комплексности, редукција полиномиалне временске сложености је метод решавања проблема помоћу хипотетичког потпрограма за решавање другачијих проблема (то јест, редукција - свођење) који користи полиномиално време искључујући време потребно потпрограму. Постоји неколико различитих типова редукције полиномиалне временске сложености, у зависности од детаља начина коришћења потпрограма. Интуитивно, редукција полиномиалне временске сложености доказује да први проблем није много тежи од другог, јер где год постоји ефикасан алгоритам за решавање другог проблема, сигурно постоји ефикасан алгоритам за решавање првог. Редукције полиномиалне временске сложености се често користе у теорији сложености за дефинисање класе сложености, као и комплетних проблема за те класе.

Типови редукције[уреди | уреди извор]

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

Многобројна редукција полиномиалне временске сложености од проблема А до проблема Б (оба од којих се углавном захтева да буду проблеми одлучивања) је алгоритам полиномиалне временске сложености за претварање улаза у проблем А у улазе у проблем Б, тако да трансформисан проблем има исти излаз као оригинални проблем. Случај „x“ проблема А може бити решен користећи ову трансформацију да произведе случај „y“ проблема Б, дајући „y“ као улаз у алгритам за проблем Б, и враћајући свој излаз. Многобројне редукције полиномиалне временске сложености могу бити познате и као полиномиалне транформације или Карпове редукције, назване по Ричард Карпу. Редукција овог типа може се означити изразом $A\leq _{m}^{P}B$ .^[1]

Редукција таблицом истинитости од проблема А до проблема Б (оба проблеми одлучивања) је алгоритам полиномиалне временске сложености за трансформацију улаза у проблем А у фиксни број улаза у проблем Б, тако да излаз оригиналног проблема може бити изражен као функција излаза за Б. Функција која мапира излазе за Б у излаз за А мора бити иста за све излазе, тако да може бити изражена таблицом истинитости. Редукција овог типа се може означити изразом $A\leq _{tt}^{P}B$ .^[2]
Турингова редукција полиномиалне временске сложености из проблема А у проблем Б је алгоритам који решава проблем А користећи полиномиални број позива до потпрограма за проблем Б, и полиномиално време изван тих потпрограмски позива. Турингове редукције полиномиалне временске сложености могу бити познате и као Кукове редукције, назване по Стефан Куку. Редукција овог типа се може означити изразом $A\leq _{T}^{P}B$ .^[1]

Најчешће коришћена редукција од ових је многобројна редукција, и у неким случајевима фраза „редукција полиномиалне временске сложености“ може бити коришћена да значи многобројну редукцију полиномиалне временске сложености.^[3]

Комплетност[уреди | уреди извор]

Проблем комплетности за дату класу сложености C и редукцију ≤ је проблем P који припада C, тако да сваки проблем А у C има редукцију A ≤ P. На пример, проблем је NP-комплетан ако припада NP и сви проблеми у NP имају многобројну редукцију полиномиалне временске сложености за њега. Проблем који припада NP се може доказати да је NP-комплетан проналажењем једне многобројне редукције полиномиалне временске сложености за њега.^[4] Многобројне редукције полиномиалне временске сложености су се користиле да дефинишу проблеме комплетности за друге класе сложености, укључујући PSPACE-комплетне језике и EXPTIME-комплетне језике.^[5]

Сваки проблем одлучивања у P (класа проблема одлучивања полиномиалне временске сложености, где нетривијално значи да нема сваки улаз исти излаз) може се упростити на сваки други нетривијални проблем, користећи многобројну редукцију полиномиалне временске сложености. Да би се трансформисао случај проблема А у Б, потребно је решити А у полиномиалном времену и потом користити решење да би се одабрао један од два случаја проблема Б са два различита одговора. Стога, за класе комплексности унутар P, као што су L, NL, NC, и само P, редукције полиномиалне временске сложености не могу бити коришћене за дефинисање комплетних језика: ако би се користиле на овај начин, сваки нетривијални проблем у P би био комплетан. Уместо тога, слабије редукције као што су лог-просторна редукција или NC редукција се користе за дефинисање класа или комплетних проблема за ове класе, као што су P-комплетни проблеми.^[6]

Дефинисање класа комплетности[уреди | уреди извор]

Дефиниције класа комплексности NP, PSPACE, и EXPTIME не укључују редукције: редукције су присутне у њиховим истраживањима само у дефиницији комплетних језика за ове класе. Међутим, у неким случајевима класа комплексности се може дефинисати редукцијом. Ако је C било који проблем одлучивања, онда се може дефинисати класа комплексности C која се састји од језика А за које важи $A\leq _{m}^{P}C$ . У овом случају, C ће аутоматски бити комплетна за C, али C је могуће да ће такође имати друге комплетне проблеме.

Пример овога је класа комплетности $\exists \mathbb {R}$ дефинисана из егзистенцијалне теорије реалних бројева, проблем израчунавања који је познат да буде NP-тежакпроблеми и у PSPACE, али није познат да буде комплетан за NP, PSPACE, или било који језик у полиноминалној хијерархији. $\exists \mathbb {R}$ је сет проблема који имају многобројну редукцију полиномиалне временске сложености до егзистенцијалне теорије реалних бројева; садржи неколико других комплетних проблема као што су одређивање праволинијског броја прелаза неусмереног графа. Сваки проблем у $\exists \mathbb {R}$ наслеђује имовину која припада PSPACE, и сваки $\exists \mathbb {R}$ -комплетан проблем је NP-тежак.^[7]

Слично, класа комплексности GI се састоји од проблема који могу бити упрошћени на проблем изоморфизма графова. Пошто је изоморфизам графова познат да припада и NP и co-AM, исто важи и за сваки проблем у овој класи. Проблем је GI-комплетан ако је комплетан за ову класу; сам проблем изоморфизма графова је GI-комплетан, као што је и неколицина других сродних проблема.^[8]

Spoljašnje veze[уреди | уреди извор]

Reference[уреди | уреди извор]

^ ^а ^б Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge University Press, стр. 59—60, ISBN 9781139472746 .
^ Buss, S.R.; Hay, L. (1988), „On truth-table reducibility to SAT and the difference hierarchy over NP”, Proceedings of Third Annual Structure in Complexity Theory Conference, стр. 224—233, doi:10.1109/SCT.1988.5282 .
^ Wegener, Ingo (2005), Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer, стр. 60, ISBN 9783540274773 .
^ Garey, Michael R.; Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman .
^ Aho, A. V. (2011), „Complexity theory”, Ур.: Blum, E. K.; Aho, A. V., Computer Science: The Hardware, Software and Heart of It, стр. 241—267, doi:10.1007/978-1-4614-1168-0_12 . See in particular p. 255.
^ Greenlaw, Raymond; Hoover, James; Ruzzo, Walter (1995), Limits To Parallel computation; P-Completeness Theory, ISBN 0-19-508591-4 . In particular, for the argument that every nontrivial problem in P has a polynomial-time many-one reduction to every other nontrivial problem, see p. 48.
^ Schaefer, Marcus (2010), „Complexity of some geometric and topological problems” (PDF), Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers, Lecture Notes in Computer Science, 5849, Springer-Verlag, стр. 334—344, doi:10.1007/978-3-642-11805-0_32 .
^ Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1993), The Graph Isomorphism Problem: Its Structural Complexity, Birkhäuser, ISBN 978-0-8176-3680-7, OCLC 246882287 .

[goldreich-1] а ^б Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge University Press, стр. 59—60, ISBN 9781139472746 .

[2] Buss, S.R.; Hay, L. (1988), „On truth-table reducibility to SAT and the difference hierarchy over NP”, Proceedings of Third Annual Structure in Complexity Theory Conference, стр. 224—233, doi:10.1109/SCT.1988.5282 .

[3] Wegener, Ingo (2005), Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer, стр. 60, ISBN 9783540274773 .

[4] Garey, Michael R.; Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman .

[5] Aho, A. V. (2011), „Complexity theory”, Ур.: Blum, E. K.; Aho, A. V., Computer Science: The Hardware, Software and Heart of It, стр. 241—267, doi:10.1007/978-1-4614-1168-0_12 . See in particular p. 255.

[6] Greenlaw, Raymond; Hoover, James; Ruzzo, Walter (1995), Limits To Parallel computation; P-Completeness Theory, ISBN 0-19-508591-4 . In particular, for the argument that every nontrivial problem in P has a polynomial-time many-one reduction to every other nontrivial problem, see p. 48.

[7] Schaefer, Marcus (2010), „Complexity of some geometric and topological problems” (PDF), Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers, Lecture Notes in Computer Science, 5849, Springer-Verlag, стр. 334—344, doi:10.1007/978-3-642-11805-0_32 .

[8] Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1993), The Graph Isomorphism Problem: Its Structural Complexity, Birkhäuser, ISBN 978-0-8176-3680-7, OCLC 246882287 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]