کاهش (پیچیدگی)

کاهش نمونه‌ای از مسئله صدق‌پذیری دودویی ( $(A\lor B)\land (\neg A\lor \neg B\lor \neg C)\land (\neg A\lor B\lor C)$) به مسئله پوشش گره‌ای. گره‌های آبی بیرون از بیضی پوششی گره‌ای کمینه را می‌سازند و گره‌های آبی درون بیضی ارزش‌دهی درست برای فرمول مسئله صدق‌پذیری دودویی

در نظریه محاسبه و نظریه پیچیدگی رایانشی، کاهش فراروندی است که یک مسئله یا مسئله را به مسئله ای دیگر می‌ترادیساند. فرض کنید که الگوریتمی برای حل مسئله «ب» داریم و می‌دانیم مسئله «ب» سخت (از دید پیچیدگی زمانی) است. اگر مسئله «آ» را بتوان به مسئله «ب» کاست، آن گاه می‌توان الگوریتم مسئله «ب» را برای حل مسئله «آ» نیز به کار برد. هم‌چنین، اگر در زمانی کوتاه مسئله «ب» کاهش‌پذیر به مسئله «آ» باشد، آن گاه می‌توان با به کار بردن رابطه‌ی هم‌ارزی نشان داد که «آ» دست کم به همان اندازه سخت است. در اینجا، کاهش بایستانه به معنای ساده کردن مسئله نیست، بلکه تنها نگاشت به مسئلهی دیگر است.

کاربردها

ما کاهش را ناخودآگاهانه به کار می‌گیریم. اگر ندانیم که چگونه باید مسئله ای را حل کنیم، می‌کوشیم که این مسئله را به مسئله ای دیگر که می‌دانیم چگونه حل می‌شود بترادیسانیم (تغییر دهیم). این فراروند کاستنِ مسئلهِ تازه به مسئله ای است که برای آن راه‌حلی داریم. با این کار، می‌توان از راه‌حل‌هایی در دست برای حل مسئله تازه بهره جست. این فراروند مسئله ناشناخته را به مسئله ای آشنا می‌ترادیساند.

هم‌چنین می‌توان مسئله ای آشنا را به مسئله ای ناشناخته کاست. این کاربرد هوشمندانه‌ی کاهش برای نشان دادن پیچیدگی مسئله ناشناخته است. فرض کنید که ما مسئله ای مانند «آ» داریم و می‌دانیم که این مسئله سخت است. هم‌چنین فرض کنید که مسئله ناشناخته‌ای مانند «ب» داریم که می‌خواهیم نشان دهیم که این مسئله نیز سخت است. اگر بتوانیم مسئله سخت «آ» را در زمانی کوتاه به مسئله «ب» بترادیسانیم، آن گاه می‌توانیم با برهان خلف نشان دهیم که مسئله «ب» نیز سخت است. برهان خلف چنین است: فرض کنید که پیرِ فرزانه‌ای هست که مسئله «ب» را در زمانی کوتاه حل می‌کند. مسئله «آ» را به مسئله «ب» بترادیسید و سپس پیر فرزانه مسئله «آ» را در زمانی کوتاه حل می‌کند. می‌دانیم که «آ» سخت است ولی پیر فرزانه «آ» را در زمانی کوتاه حل کرده است. این پادگویی (تناقض) است. بنا بر پادگویی، مسئله «ب» نیز سخت است.

تعریف

فرض کنید دو زیرمجموعه‌ی A و B از N و مجموعه‌ای از تابع‌های F از N به N که زیر پیوند تابع‌ها بسته‌اند، داده شده‌اند. گوییم A زیر F از B کاهش‌پذیر است اگر:

.$\exists f\in F,\forall x\in \mathbb {N} :x\in A\Leftrightarrow f(x)\in B$

و می‌نویسیم:

$A\leq _{F}B$.

فرض کنید $S$ زیرمجموعه‌ای از $P(N)$ و $\leq _{a}$ یک کاهش است. گوییم $S$ زیر ≥ بسته است اگر:

.$\forall s\in S,\forall A\in P(N):A\leq s\Rightarrow A\in S$

زیرمجموعهٔ A از N برای $S$ سخت نامیده می‌شود، اگر:

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

زیرمجموعهٔ A از N برای $S$ کامل خوانده می‌شود اگر A سخت باشد و A در $S$ باشد.

نمونه

برای نشان دادن اینکه مسئلهٔ تصمیم P، تصمیم‌ناپذیر است، باید مسئله ای تصمیمی را که تصمیم‌ناپذیر است به P کاست. فراروند کاهش باید در زمانی کوتاه انجام پذیرد. نشان می‌دهیم که مسئله P تصمیم‌ناپذیر است اگر مسئلهٔ توقف به P کاسته شود.

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «(Reduction (complexity». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۳ تیر ۹۲.