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

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

Типови редукције

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

Многобројна редукција полиномијалне временске сложености од проблема А до проблема Б (оба од којих се углавном захтева да буду проблеми одлучивања) је алгоритам полиномијалне временске сложености за претварање улаза у проблем А у улазе у проблем Б, тако да трансформисан проблем има исти излаз као оригинални проблем. Случај „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]

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 pp. 255.
^ Greenlaw, Raymond; Hoover, James; Ruzzo, Walter (1995), Limits To Parallel computation; P-Completeness Theory, ISBN 978-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 pp. 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 pp. 255.

[6] Greenlaw, Raymond; Hoover, James; Ruzzo, Walter (1995), Limits To Parallel computation; P-Completeness Theory, ISBN 978-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 pp. 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]