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

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

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

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

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

و می‌نویسیم:

${\displaystyle A{\le }_{F}B}$

.

فرض کنید ${\displaystyle S}$

.${\displaystyle \mathrm{\forall }s\in S,\mathrm{\forall }A\in P(N):A\le s\Rightarrow A\in S}$

زیرمجموعهٔ A از N برای ${\displaystyle S}$

.${\displaystyle \mathrm{\forall }s\in S\text{. }s\le A}$

زیرمجموعهٔ A از N برای ${\displaystyle S}$

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