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

از ویکی‌پدیا، دانشنامهٔ آزاد
(تغییرمسیر از تقلیل (پیچیدگی))
پرش به: ناوبری، جستجو

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

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

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

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

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

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

.

و می‌نویسیم:

.

فرض کنید زیرمجموعه‌ای از و یک کاهش باشد، در این صورت می‌گوییم تحت ≥ بسته است اگر:

.

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

.

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

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

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

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

نمونه[ویرایش]

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

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

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