Svođenje (teorija računske složenosti)

Iz Vikipedije, slobodne enciklopedije
Idi na navigaciju Idi na pretragu
Primer svođenja od SAT problem (AB) ∧ (¬A ∨ ¬B ∨ ¬C) ∧ (¬ABC) do Pokrivač čvorova. Plavi čvorovi formiraju minimalan pokrivač čvorova, i plavi čvorovi u sivom ovalu odgovaraju zadovoljavajućem istinitom zadatku za originalnu formulu.

U teoriji izračunljivosti i teoriji složenosti, svođenje je algoritam za pretvaranje jednog problema u drugi problem. Svođenje od jednog do drugog roblema može se koristiti da pokaže da je drugi problem težak isto koliko i prvi problem.

Intuitivno, problem A se može svesti na problem B ako je algoritam za B efikasan za rešavanje problema (ako je postojao) takođe može da se koristi kao potprogram za efikasno rešavanje problema A. Kada je to tačno, rešavanje A ne može biti teže nego rešavanje V. "Teže" znači imati veću procenu potrebnih računarskih sredstava u datom kontekstu (npr. veću vremensku složenost, itd.).

Pišemo A ≤m B, obično sa indeksom na ≤ da ukaže na vrstu svođenja koja se koristi (m : svođenje mapiranja, p : polinomijalno svođenje).

Matematička struktura generiše niz problema smanjenjem određene vrste uopštene forme prethodno uređenog algoritma, čija ekvivalencija klase može da se koristi za definisanje stepena nerešivosti i složenosti klase.

Uvod[uredi]

Postoje dve glavne situracije u kojima moramo da koristimo svođenje:

  • Prvo: nalazimo samo rešenje problema koje je slično problemu koji smo već rešili. U ovim slučajevima, često brz način rešavanja novog problema je da svaki slučaj novog problema transformiše u slučaj starog problema, rešite to koristeći naše postojeće rešenje, a zatim koristeći ovo da dobijete naše konačno rešenje. Ovo je možda najočiglednija upotreba svođenja.
  • Drugo: pretpostavimo da imamo problem koji je dokazano teško rešiti, i imamo sličan novi problem. Mogli bismo posumnjati da je isto tako težak da se reši. Mi tvrdimo suprotno: pretpostavimo da je novi problem lako resiti. Onda, ako možemo pokazati da se svaki slučaj starog problema rešava lako pretvarajući ga u slučaj novog problema i rešavanje ovih, imamo kontradikciju. Ovo pokazuje da je novi problem takođe težak.

Veoma jednostavn primer svođenja je kvadratno množenje. Pretpostavimo da svi znamo kako da sabiramo, oduzimamo, kvadriramo i delimo sa dva. Možemo koristiti ovo znanje u kombinaciji sa sledećom formulom, da se dobije proizvod bilo koja dva broja:

Takođe imamo svođenje u drugom pravcu; Očigledno, ako možemo pomnožiti dva broja, možemo kvadrirati broj. Ovo proizilazi da su ova dva problema podjednako teška. Ova vrsta svođenja odgovara Tjuringovom svođenju.

Međutim, svođenje postaje mnogo teže, ako dodamo ograničenje možemo da koristimo samo jednom kvadratnu funkciju, i tek na kraju. U ovom slučaju, čak i ako je dozvoljeno da koristite sve osnovne aritmetičke operacije, uključujući i množenje, ne svođenje postoji uopšte, jer da bi dobili željeni rezultat kvadrata prvo moramo da računamo kvadratni koren, i to kvadratni koren može biti iracionalan broj da ne može biti izgrađen od aritmetičke operacije na racionalnim brojevima. Odlazak u drugom pravcu, međutim, možemo sigurno kvadritati broj sa samo jednim množenjem, tek na kraju. Koristeći ovaj ograničeni oblik svođenja, pokazali smo da iznenađuje rezultat čije je množenje u celini teže od kvadriranja. To odgovara jednom-više svođenju.

Definicija[uredi]

Imajući u vidu dva podskupa A i V od N i skup fukncija F od N do N koja je zatvorena u sastavu, A se može svesti na V pod F ako:

Pišemo

Neka je S podskup od P(N) i ≤ svođenje, tada se S naziva zatvoreno pod ≤ ako

Podskup A od N zove se čvrst za S ako

Podskup A od N se zove potpun za S ako je A težak za S i A je u S.

Svojstva[uredi]

Svođenje je unapred uređeni algoritam, to je refleksivan i tranzitivan odnos na P(NP(N), gde je P(N) partitivni skup prirodnih brojeva.

Vrste i promene svođenja[uredi]

Kao što je već opisano u prethodnom primeru, postoje dve osnovne vrste svođenja koje se koriste u računarskoj složenosti, jedno-više svođenje i Tjuringovo svođenje. Jedno-više svođenje plana slučajeva jednog problema na slučajeve drugog; Tjuringovo svođenje izračunava rešenje za jedan problem, pretpostavljajući da je drugi probelm lako rešiti. Jedno-više svođenje je moćniji tip Tjuringovog svođenja, i efikasnije odvajanje problema u razičite klase složeosti. Međutim, povećana ograničenja na jedno-više svođenje ih teže nalazi.

Problem je potpun za složenost klasa ako se svaki problem u klasi svodi na taj problem, a takođe je u samoj klasi. U tom smislu, problem predstavlja klasu, jer svako rešenje za to može, u kombinaciji sa svođenjem, da se korsiti za rešavanje svih problema u klasi.

Međutim, da bi bili korisni, svođenje mora biti lako. Na primer, sasvim je moguće smanjiti težak-za-rešiti NP-kompletni problemi kao što je problem zadovoljivosti na beznačajnim problemima. Kao utvrđivanje da li je broj jednak nili, tako da je svođenje uređeno da reši problem u eksponencijalnom vremenu i izlaz je nula samo ukolikko postoji rešenje. Međutim, ovo ne ostvaruje mnogo, jer iako možemo rešiti novi problem, predstavljanje svođenja je jednako teško kao rešavanje starih problema. Isto tako, računarsko svođenje fukncije izračunljivosti može da smanji neodlučiv problem u jedan odlučiv. Michael Sipser ističe u Uvodu u Teoriju računanja: "Svođenje mora biti lako, u odnosu na složenost tipičnih problema u klasi [...] Ako je samo svođenje bilo teško izračunati, jednostavno rešenje za potpun problem ne bi nužno dao jednostavno rešenje za probleme svođenjem na njega."

Dakle, odgovarajući pojam svođenja zavisi od složenosti klasa koje se proučavaju. Kada koristi proučavanje složenosti klasa NP (klasa kompleksnosti) i teže klase kao što su polinomijalna hijerarhija, polinomijalno vreme svođenja. Tokom studija časove u okviru P kao što su NC i NL, logaritamsko-prostorno svođenje koriste. Svođenje se korsti u teoriji izračunljivosti da pokaže da li su problemi rešivi ili nisu, od strane uređaja, uopšte; u ovom slučaju, svođenje se ograničava samo na izračunljivu funkciju.

U slučaju optimizacije (maksimizacije ili minimizacije) problema, mi često mislimo u smoslu približavanja-očuvanja svođenja. Pretpostavimo da imamo dva problema optimizacije tako da se slučaj jednog problema preslikava u slučaj drugog, tako da skoro optimalno rešenje za slučajeve drugog problema mogu da se transformišu unazad da bi se došlo do optimalnih rešenja za raniji. Na ovaj način, ako imamo optimizaciju algoritma ili (aproksimacioni algoritam) koji pronalazi skoro optimalna (ili optimalna) rešenja za slučajeve problema V, i efikasno probližavanje-očuvanje svođenja od problema A do problema V, po sastavu dobijamo optimizaciju algoritma koji daje skoro optimačna rešenja za slučajeve problema A. Svođenje približavanja-očuvanja se često koristi da se dokaže čvrstina približavanja rezultata: ako je neki optimizacioni problem A teško približiti (pod nekom složenom pretpostavkom) u okviru boljeg faktora α za α, i tu je svođenje β-približavanje-očuvanje za problem A do problema V, mi možemo odlućiti da je problem V teško približiti u okviru faktora α/β.

Primeri[uredi]

  • Da bi pokazao da je Problem odlučivanja P neodlučiv moramo naći smanjenje problema odlučivanja za koji je već poznato da je neodlučiv za P. Ta funkcija smanjenja mora biti izračunljiva funkcija. Konkretno, mi često smatramo da je problem P neodlučiv pokazujući da se zaustavljanje problema smanjuje na P.
  • Nastavak kompleksnosti P, NP i PSPACE je zatvoren pod (više-jedan, "Karp") polinoma vremena smanjenja.
  • Složenosti klasa L, NL, P, NP i PSPACE su zatvorene pod uticajem smanjenja prostora.

Detaljan primer[uredi]

Sledeći primer pokazuje kako se koristi smanjenje problema da dokaže da je jezik neodlučiv. Pretpostavimo da je H(M, w) problem određivanja da li se data Tjuringova mašina zaustavlja (prihvatanjem ili odbijanjem) na ulazu sa stringom w. Pretpostavimo da je E(M) ) problem određivanja da li jezik date Tjuringove mašine M prihvata ili je prazna (drugim rečima, da li M prihvata nekakve veze uopšte). Mi smo pokazali da je E neodlučiv redukcijom dobijenom od H.

Da biste dobili kontradikciju, pretpostavimo da je R je decider za E. Mi ćemo koristiti S za proizvodnju H (što znamo ne postoji). S obzirom na ulaz M i w (za Tjuring mašine i neke ulaznog stringa), defišemo S(M, w) sledećim ponašanjem: S stvara Tjuring mašine N da prihvate samo ako je ulazan string je N je w i M zaustavlja na ulazu w, i ne zaustavlja se drugačije. Odlučujuć S sada može oceniti R(N) da proveri da li je jezik prihvaćen od strane N prazanog. Ako R prihvata N, onda je jezik prihvaćen od strane N prazanog, tako da se u određenom M ne zaustavljaju na ulazu' pod w, pa S mogu odbijati. Ako R odbacuje N, onda jezik prihvaćen od strane N nije prazan M ne stoji na ulazuw, pa S može da prihvati. Dakle, ako bismo imali odlučujuć R za E, bili bismo u stanju da proizvedemo odlučujuć S za zaustavljanje problema H(M, w) za bilo koju mašinu M i ulazw. Pošto znamo da takva S ne može da postoji, sledi da je jezik E takođe neodlučiv.

Literatura[uredi]

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms. MIT Press.2001. ISBN 978-0-262-03293-3.
  • Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability, McGraw-Hill. 1967. ISBN 978-0-262-68052-3.
  • Peter Bürgisser: Completeness and Reduction in Algebraic Complexity Theory, Springer. 2000. ISBN 978-3-540-66752-0.
  • E.R. Griffor: Handbook of Computability Theory, North Holland. 1999. ISBN 978-0-444-89882-1.