Korisnik:VikiNikolaKostadinovic/pesak

Redukcija polinomialne vremenske složenosti

U teoriji kompleksnosti, redukcija polinomialne vremenske složenosti je metod rešavanja problema pomoću hipotetičkog potprograma za rešavanje drugačijih problema (to jest, redukcija - svođenje) koji koristi polinomialno vreme isključujući vreme potrebno potprogramu. Postoji nekoliko različitih tipova redukcije polinomialne vremenske složenosti, u zavisnosti od detalja načina korišćenja potprograma. Intuitivno, redukcija polinomialne vremenske složenosti dokazuje da prvi problem nije mnogo teži od drugog, jer gde god postoji efikasan algoritam za rešavanje drugog problema, sigurno postoji efikasan algoritam za rešavanje prvog. Redukcije polinomialne vremenske složenosti se često koriste u teoriji složenosti za definisanje klase složenosti, kao i kompletnih problema za te klase.

Tipovi redukcije

Tri najčešća tipa redukcije polinomialne vremenske složenosti su, od najviše do najmanje ograničavajućih, mnogobrojna redukcija, redukcija tablicom istinitosti, i Turingova redukcija.

Mnogobrojna redukcija polinomialne vremenske složenosti od problema A do problema B (oba od kojih se uglavnom zahteva da budu problemi odlučivanja) je algoritam polinomialne vremenske složenosti za pretvaranje ulaza u problem A u ulaze u problem B, tako da transformisan problem ima isti izlaz kao originalni problem. Slučaj „x“ problema A može biti rešen koristeći ovu transformaciju da proizvede slučaj „y“ problema B, dajući „y“ kao ulaz u algritam za problem B, i vraćajući svoj izlaz. Mnogobrojne redukcije polinomialne vremenske složenosti mogu biti poznate i kao polinomialne tranformacije ili Karpove redukcije, nazvane po Ričard Karpu. Redukcija ovog tipa može se označiti izrazom $A\leq _{m}^{P}B$ .^[1]

Redukcija tablicom istinitosti od problema A do problema B (oba problemi odlučivanja) je algoritam polinomialne vremenske složenosti za transformaciju ulaza u problem A u fiksni broj ulaza u problem B, tako da izlaz originalnog problema može biti izražen kao funkcija izlaza za B. Funkcija koja mapira izlaze za B u izlaz za A mora biti ista za sve izlaze, tako da može biti izražena tablicom istinitosti. Redukcija ovog tipa se može označiti izrazom $A\leq _{tt}^{P}B$ .^[2]
Turingova redukcija polinomialne vremenske složenosti iz problema A u problem B je algoritam koji rešava problem A koristeći polinomialni broj poziva do potprograma za problem B, i polinomialno vreme izvan tih potprogramski poziva. Turingove redukcije polinomialne vremenske složenosti mogu biti poznate i kao Kukove redukcije, nazvane po Stefan Kuku. Redukcija ovog tipa se može označiti izrazom $A\leq _{T}^{P}B$ .^[1]

Najčešće korišćena redukcija od ovih je mnogobrojna redukcija, i u nekim slučajevima fraza „redukcija polinomialne vremenske složenosti“ može biti korišćena da znači mnogobrojnu redukciju polinomialne vremenske složenosti.^[3]

Kompletnost

Problem kompletnosti za datu klasu složenosti C i redukciju ≤ je problem P koji pripada C, tako da svaki problem A u C ima redukciju A ≤ P. Na primer, problem je NP-kompletan ako pripada NP i svi problemi u NP imaju mnogobrojnu redukciju polinomialne vremenske složenosti za njega. Problem koji pripada NP se može dokazati da je NP-kompletan pronalaženjem jedne mnogobrojne redukcije polinomialne vremenske složenosti za njega.^[4] Mnogobrojne redukcije polinomialne vremenske složenosti su se koristile da definišu probleme kompletnosti za druge klase složenosti, uključujući PSPACE-kompletne jezike i EXPTIME-kompletne jezike.^[5]

Svaki problem odlučivanja u P (klasa problema odlučivanja polinomialne vremenske složenosti, gde netrivijalno znači da nema svaki ulaz isti izlaz) može se uprostiti na svaki drugi netrivijalni problem, koristeći mnogobrojnu redukciju polinomialne vremenske složenosti. Da bi se transformisao slučaj problema A u B, potrebno je rešiti A u polinomialnom vremenu i potom koristiti rešenje da bi se odabrao jedan od dva slučaja problema B sa dva različita odgovora. Stoga, za klase kompleksnosti unutar P, kao što su L, NL, NC, i samo P, redukcije polinomialne vremenske složenosti ne mogu biti korišćene za definisanje kompletnih jezika: ako bi se koristile na ovaj način, svaki netrivijalni problem u P bi bio kompletan. Umesto toga, slabije redukcije kao što su log-prostorna redukcija ili NC redukcija se koriste za definisanje klasa ili kompletnih problema za ove klase, kao što su P-kompletni problemi.^[6]

Definisanje klasa kompletnosti

Definicije klasa kompleksnosti NP, PSPACE, i EXPTIME ne uključuju redukcije: redukcije su prisutne u njihovim istraživanjima samo u definiciji kompletnih jezika za ove klase. Međutim, u nekim slučajevima klasa kompleksnosti se može definisati redukcijom. Ako je C bilo koji problem odlučivanja, onda se može definisati klasa kompleksnosti C koja se sastji od jezika A za koje važi $A\leq _{m}^{P}C$ . U ovom slučaju, C će automatski biti kompletna za C, ali C je moguće da će takođe imati druge kompletne probleme.

Primer ovoga je klasa kompletnosti $\exists \mathbb {R}$ definisana iz egzistencijalne teorije realnih brojeva, problem izračunavanja koji je poznat da bude NP-težakproblemi i u PSPACE, ali nije poznat da bude kompletan za NP, PSPACE, ili bilo koji jezik u polinominalnoj hijerarhiji. $\exists \mathbb {R}$ je set problema koji imaju mnogobrojnu redukciju polinomialne vremenske složenosti do egzistencijalne teorije realnih brojeva; sadrži nekoliko drugih kompletnih problema kao što su određivanje pravolinijskog broja prelaza neusmerenog grafa. Svaki problem u $\exists \mathbb {R}$ nasleđuje imovinu koja pripada PSPACE, i svaki $\exists \mathbb {R}$ -kompletan problem je NP-težak.^[7]

Slično, klasa kompleksnosti GI se sastoji od problema koji mogu biti uprošćeni na problem izomorfizma grafova. Pošto je izomorfizam grafova poznat da pripada i NP i co-AM, isto važi i za svaki problem u ovoj klasi. Problem je GI-kompletan ako je kompletan za ovu klasu; sam problem izomorfizma grafova je GI-kompletan, kao što je i nekolicina drugih srodnih problema.^[8]

Spoljašnje veze

Reference

^ ^a ^b Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge University Press, str. 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, str. 224—233, doi:10.1109/SCT.1988.5282 .
^ Wegener, Ingo (2005), Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer, str. 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”, Ur.: Blum, E. K.; Aho, A. V., Computer Science: The Hardware, Software and Heart of It, str. 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, str. 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, str. 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, str. 224—233, doi:10.1109/SCT.1988.5282 .

[3] Wegener, Ingo (2005), Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer, str. 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”, Ur.: Blum, E. K.; Aho, A. V., Computer Science: The Hardware, Software and Heart of It, str. 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, str. 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]