تقلیل (پیچیدگی)

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

مسئله A به مسئله B تقلیل‌پذیر است اگر الگوریتم کارا برای حل مسئلهٔ B (در صورت وجود)، را بتوان برای حل کارای مسئلهٔ A نیز استفاده کرد. دراین صورت حل‌کردن مسئله A نمی‌تواند سخت‌تر از حل کردن مسئلهٔ B باشد و می‌نویسیم A ≤m B، معمولاً زیرنویس ≥ برای نشان دادن نوع کاهش است (m: نگاشت تقلیل و p: تقلیل چندجمله‌ای).

مقدمه[ویرایش]

اغلب ما برای پیداکردن حل مسئلهٔ خود، سعی می‌کنیم با استفاده از مسائلی شبیه این مسئله، که قبلاً آن‌ها را حل کرده‌ایم، مسئلهٔ خود را حل کنیم. در این موارد، اغلب یک راه سریع حل مسئله جدید این است که هر نمونه از مسئله جدید را به نمونه‌ای از مسئله قدیمی تبدیل کنیم و سپس با استفاده از راه‌حل‌های موجود، آن‌ها را حل کنیم و آن را برای مشخص کردن جواب اصلی بکار ببریم. این راه شاید واضح‌ترین راه استفاده از تقلیل است.

یک راه دیگر استفاده زیرکانه از این روش این‌است که: فرض کنید ما یک مسئله داریم که اثبات کرده‌ایم که حل آن سخت است و یک مسئلهٔ جدید دیگر شبیه به آن داریم. ما ممکن است حدس بزنیم که حل این مسئله نیز سخت است. با استفاده از تناقض اثبات می‌کنیم: فرض کنید که حل مسئله جدید آسان باشد. اگر ما نشان بدهیم که هر نمونه از مسئلهٔ قدیمی به راحتی با تبدیل آن به نمونه‌ای از مسئله جدید قابل حل است و آن‌ها را حل کنیم، به تناقض رسیده‌ایم. این ثابت می‌کند که مسئلهٔ جدید نیز سخت است.

تعریف[ویرایش]

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

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

و می‌نویسیم:

A \leq_{F} B .

فرض کنید S زیرمجموعه‌ای ازP(N) و  \leq_{a} یک کاهش باشد، در این صورت می‌گوییم 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 سخت باشد و A در S باشد.

کابرد[ویرایش]

یک مسئله برای کلاس پیچیدگی کامل است اگر هر مسئله در کلاس به آن مسئله کاهش پیدا کند و آن نیز در کلاس خودش باشد، به این معنا که هر حلی برای این مسئله می‌تواند در ترکیب با کاهش، برای حل مسائل این کلاس مورد استفاده قرار گیرد.

بااین‌حال، برای اینکه مفید باشد، باید کاهش آسان باشد. برای مثال کاهش مسئله‌ی با حل سخت ان‌پی کامل، مثلاً مسئله‌ی مسئله صدق‌پذیری دودویی به یک مسئله بدیهی، مانند تشخیص صفر بودن یک عدد، با داشتن ماشین کاهش حل مسئله در زمان نمایی و خروجی صفر در صورت داشتن جواب، کاملاً امکان‌پذیر است.

مثال[ویرایش]

برای نشان دادن اینکه مسئلهٔ تصمیم P، تصمیم‌ناپذیر است، باید یک کاهش از مسئله‌ی تصمیم که در حال حاضر بعنوان تصمیم‌ناپذیر شناخته شده است، به P پیدا کنیم. تابع کاهش باید تابعی محاسبه‌پذیر باشد. بطور خاص ما نشان می‌دهیم که مسئله P تصمیم‌ناپذیر است، با نشان دادن اینکه مسئله‌ی توقف به P کاهش پیدا می‌کند.

منابع[ویرایش]

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