Свођење (теорија рачунске сложености)

Пример свођења од САТ проблем (A ∨ B) ∧ (¬A ∨ ¬B ∨ ¬C) ∧ (¬A ∨ B ∨ C) до Покривач чворова. Плави чворови формирају минималан покривач чворова, и плави чворови у сивом овалу одговарају задовољавајућем истинитом задатку за оригиналну формулу.

У теорији израчунљивости и теорији сложености, свођење је алгоритам за претварање једног проблема у други проблем. Свођење од једног до другог роблема може се користити да покаже да је други проблем тежак исто колико и први проблем.

Интуитивно, проблем А се може свести на проблем Б ако је алгоритам за Б ефикасан за решавање проблема (ако је постојао) такође може да се користи као потпрограм за ефикасно решавање проблема А. Када је то тачно, решавање А не може бити теже него решавање В. "Теже" значи имати већу процену потребних рачунарских средстава у датом контексту (нпр. већу временску сложеност, итд.).

Пишемо A ≤_m B, обично са индексом на ≤ да укаже на врсту свођења која се користи (m : свођење мапирања, p : полиномијално свођење).

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

Увод

Постоје две главне ситурације у којима морамо да користимо свођење:

• Прво: налазимо само решење проблема које је слично проблему који смо већ решили. У овим случајевима, често брз начин решавања новог проблема је да сваки случај новог проблема трансформише у случај старог проблема, решите то користећи наше постојеће решење, а затим користећи ово да добијете наше коначно решење. Ово је можда најочигледнија употреба свођења.
• Друго: претпоставимо да имамо проблем који је доказано тешко решити, и имамо сличан нови проблем. Могли бисмо посумњати да је исто тако тежак да се реши. Ми тврдимо супротно: претпоставимо да је нови проблем лако ресити. Онда, ако можемо показати да се сваки случај старог проблема решава лако претварајући га у случај новог проблема и решавање ових, имамо контрадикцију. Ово показује да је нови проблем такође тежак.

Веома једноставн пример свођења је квадратно множење. Претпоставимо да сви знамо како да сабирамо, одузимамо, квадрирамо и делимо са два. Можемо користити ово знање у комбинацији са следећом формулом, да се добије производ било која два броја:

$a\times b={\frac {\left(\left(a+b\right)^{2}-a^{2}-b^{2}\right)}{2}}$

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

Међутим, свођење постаје много теже, ако додамо ограничење можемо да користимо само једном квадратну функцију, и тек на крају. У овом случају, чак и ако је дозвољено да користите све основне аритметичке операције, укључујући и множење, не свођење постоји уопште, јер да би добили жељени резултат квадрата прво морамо да рачунамо квадратни корен, и то квадратни корен може бити ирационалан број ${\sqrt {2}}$ да не може бити изграђен од аритметичке операције на рационалним бројевима. Одлазак у другом правцу, међутим, можемо сигурно квадритати број са само једним множењем, тек на крају. Користећи овај ограничени облик свођења, показали смо да изненађује резултат чије је множење у целини теже од квадрирања. То одговара једном-више свођењу.

Дефиниција

Имајући у виду два подскупа А и В од N и скуп фукнција F од N до N која је затворена у саставу, А се може свести на В под F ако: $\exists f\in F{\mbox{ . }}\forall x\in \mathbb {N} {\mbox{ . }}x\in A\iff f(x)\in B$

Пишемо

$A\leq _{F}B$

Нека је S подскуп од P(N) и ≤ свођење, тада се S назива затворено под ≤ ако

$\forall s\in S{\mbox{ . }}\forall A\in P(N){\mbox{ . }}A\leq s\Rightarrow A\in S$

Подскуп A од N зове се чврст за S ако

$\forall s\in S{\mbox{ . }}s\leq A$

Подскуп A од N се зове потпун за S ако је A тежак за S и A је у S.

Својства

Свођење је унапред уређени алгоритам, то је рефлексиван и транзитиван однос на P(N)×P(N), где је P(N) партитивни скуп природних бројева.

Врсте и промене свођења

Као што је већ описано у претходном примеру, постоје две основне врсте свођења које се користе у рачунарској сложености, једно-више свођење и Тјурингово свођење. Једно-више свођење плана случајева једног проблема на случајеве другог; Тјурингово свођење израчунава решење за један проблем, претпостављајући да је други пробелм лако решити. Једно-више свођење је моћнији тип Тјуринговог свођења, и ефикасније одвајање проблема у разичите класе сложеости. Међутим, повећана ограничења на једно-више свођење их теже налази.

Проблем је потпун за сложеност класа ако се сваки проблем у класи своди на тај проблем, а такође је у самој класи. У том смислу, проблем представља класу, јер свако решење за то може, у комбинацији са свођењем, да се корсити за решавање свих проблема у класи.

Међутим, да би били корисни, свођење мора бити лако. На пример, сасвим је могуће смањити тежак-за-решити НП-комплетни проблеми као што је проблем задовољивости на безначајним проблемима. Као утврђивање да ли је број једнак нили, тако да је свођење уређено да реши проблем у експоненцијалном времену и излаз је нула само уколикко постоји решење. Међутим, ово не остварује много, јер иако можемо решити нови проблем, представљање свођења је једнако тешко као решавање старих проблема. Исто тако, рачунарско свођење фукнције израчунљивости може да смањи неодлучив проблем у један одлучив. Michael Sipser истиче у Уводу у Теорију рачунања: "Свођење мора бити лако, у односу на сложеност типичних проблема у класи [...] Ако је само свођење било тешко израчунати, једноставно решење за потпун проблем не би нужно дао једноставно решење за проблеме свођењем на њега."

Дакле, одговарајући појам свођења зависи од сложености класа које се проучавају. Када користи проучавање сложености класа НП (класа комплексности) и теже класе као што су полиномијална хијерархија, полиномијално време свођења. Током студија часове у оквиру P као што су NC и NL, логаритамско-просторно свођење користе. Свођење се корсти у теорији израчунљивости да покаже да ли су проблеми решиви или нису, од стране уређаја, уопште; у овом случају, свођење се ограничава само на израчунљиву функцију.

У случају оптимизације (максимизације или минимизације) проблема, ми често мислимо у смослу приближавања-очувања свођења. Претпоставимо да имамо два проблема оптимизације тако да се случај једног проблема пресликава у случај другог, тако да скоро оптимално решење за случајеве другог проблема могу да се трансформишу уназад да би се дошло до оптималних решења за ранији. На овај начин, ако имамо оптимизацију алгоритма или (апроксимациони алгоритам) који проналази скоро оптимална (или оптимална) решења за случајеве проблема В, и ефикасно проближавање-очување свођења од проблема А до проблема В, по саставу добијамо оптимизацију алгоритма који даје скоро оптимачна решења за случајеве проблема А. Свођење приближавања-очувања се често користи да се докаже чврстина приближавања резултата: ако је неки оптимизациони проблем А тешко приближити (под неком сложеном претпоставком) у оквиру бољег фактора α за α, и ту је свођење β-приближавање-очување за проблем А до проблема В, ми можемо одлућити да је проблем В тешко приближити у оквиру фактора α/β.

Примери

• Да би показао да је Проблем одлучивања P неодлучив морамо наћи смањење проблема одлучивања за који је већ познато да је неодлучив за P. Та функција смањења мора бити израчунљива функција. Конкретно, ми често сматрамо да је проблем P неодлучив показујући да се заустављање проблема смањује на P.
• Наставак комплексности P, NP и PSPACE је затворен под (више-један, "Карп") полинома времена смањења.
• Сложености класа L, NL, P, NP и PSPACE су затворене под утицајем смањења простора.

Детаљан пример

Следећи пример показује како се користи смањење проблема да докаже да је језик неодлучив. Претпоставимо да је H(M, w) проблем одређивања да ли се дата Тјурингова машина зауставља (прихватањем или одбијањем) на улазу са стрингом w. Претпоставимо да је E(M) ) проблем одређивања да ли језик дате Тјурингове машине M прихвата или је празна (другим речима, да ли М прихвата некакве везе уопште). Ми смо показали да је Е неодлучив редукцијом добијеном од H.

Да бисте добили контрадикцију, претпоставимо да је R је децидер за E. Ми ћемо користити S за производњу H (што знамо не постоји). С обзиром на улаз M и w (за Тјуринг машине и неке улазног стринга), дефишемо S(M, w) следећим понашањем: S ствара Тјуринг машине N да прихвате само ако је улазан стринг је N је w и M зауставља на улазу w, и не зауставља се другачије. Одлучујућ S сада може оценити R(N) да провери да ли је језик прихваћен од стране N празаног. Ако R прихвата N, онда је језик прихваћен од стране N празаног, тако да се у одређеном M не заустављају на улазу' под w, па S могу одбијати. Ако R одбацује N, онда језик прихваћен од стране N није празан M не стоји на улазуw, па S може да прихвати. Дакле, ако бисмо имали одлучујућ R за E, били бисмо у стању да произведемо одлучујућ S за заустављање проблема H(M, w) за било коју машину M и улазw. Пошто знамо да таква S не може да постоји, следи да је језик E такође неодлучив.

Литература

• 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.