کاهش پیچیدگی

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

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

مقدمه

ما اغلب در حال تلاش برای حل مسائلی هستیم که شبیه به مسائلی که تاکنون حل کرده‌ایم می‌باشند. در این موارد، اغلب یک راه سریع حل مسئلهٔ جدید ، انتقال هر نمونهٔ مسئلهٔ جدید به نمونه‌هایی از مسئلهٔ قدیمی است، و آن‌ها را با راه حلهای موجود حل می‌کنیم و سپس از آن‌ها برای بدست آوردن راه حل نهایی استفاده می‌کنیم. این شاید مشهودترین استفاده از کاهشها باشد. یک استفادهٔ ماهرانه تر این است: فرض کنید که مسئله‌ای داریم که می‌دانیم حل کردن آن سخت است، و یک مسئلهٔ جدید مشابه داریم. ما ممکن است گمان کنیم که حل آن نیز سخت است. ما با تناقض بحث می‌کنیم: فرض کنید که حل کردن مسئلهٔ جدید آسان باشد. آنگاه، اگر نشان دهیم که هر نمونه از مسئلهٔ قدیمی می‌تواند به راحتی با انتقال به نمونه‌هایی از مسئله‌های جدید حل شود، و آن‌ها را حل کند، با یک تناقض رو به رو می‌شویم. این بیان می‌کند که مسئلهٔ جدید نیز سخت است. یک مثال بسیار ساده از کاهش، تبدیل از ضرب به مربع کردن است. فرض کنید که ما فقط جمع، تفریق و مربع کردن و تقسیم بر ۲ را بلد هستیم. ما می‌توانیم از این دانش که با فرمول زیر ترکیب شده‌است برای بدست آوردن ضرب هر دو عدد استفاده کنیم: A*b=((a+b)^2-a^2-b^2)/2

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

ویژگی‌ها

یک کاهش، یک مرتبه بندی پیش است که یک رابطهٔ بازتابی و متعدی در (P(N)×P(N است که در آن (P(N یک مجموعهٔ توانی از اعداد طبیعی است. انواع و کاربردهای کاهش همانطور که در مثال بالا توصیف شد، دو نوع اصلی کاهش وجود دارد که در پیچیدگی محاسباتی استفاده می‌شود، کاهش چند به یک و کاهش چرخشی. کاهش چند به یک، نمونه‌های یک مسئله را به نمونه‌هایی از دیگری می‌نگارد. کاهشهای چرخشی، جواب یک مسئله را محاسبه می‌کند و فرض می‌کند که حل مسئلهٔ دیگر آسان است. کاهش چند به یک، قویتر از کاهش چرخشی است و در هنگام جداسازی مسایل به کلاسهای پیچیدگی متفاوت، کاراتر است. اگرچه محدودیتهای فزاینده در کاهشهای چند به یک، یافتن آن‌ها را مشکلتر می‌کند. یک مسئله برای یک کلاس پیچیدگی کامل است اگر که هر مسئله در کلاس به آن مسئله کاهش یابد و خود آن نیز در کلاس باشد. در این کار، مسئله، کلاس را نشان می‌دهد، از آنجا که راه حل آن می‌تواند در ترکیب با کاهشها، برای حل هر مسئله در کلاس استفاده شود. اگرچه برای مفید بودن، کاهشها باید آسان باشند. به‌طور مثال، کاملاً ممکن است که یک مسئلهٔ NP-complete مانند مسئلهٔ رضایت بخشی بولی که حل آن مشکل است را به یک مسئلهٔ بدیهی مانند تشخیص اینکه آیا آن عدد مساوی صفر است، با داشتن ماشین کاهش که مسئله را اگر جواب داشته باشد در زمان توانی حل می‌کند و خروجی صفر را می‌دهد تبدیل کنیم. اگرچه، این چیز زیادی حاصل نمی‌کند، زیرا با اینکه ما می‌توانیم مسئلهٔ جدید را حل کنیم، اجرای کاهش، به اندازهٔ حل مسئلهٔ قدیمی سخت است. به‌طور مشابه، کاهشی که یک تابع غیرقابل محاسبه را محاسبه می‌کند می‌تواند یک مسئلهٔ تصمیم ناپذیر را به مسئلهٔ تصمیم پذیر تبدیل کند. همانطور که مایکل سیپسردر مقدمه‌ای بر نظریه محاسبه، اشاره می‌کند، اگر محاسبهٔ خود کاهش مشکل بود، کاهش باید نسبت به پیچیدگی مسائل معمولی در کلاس [...]، ساده باشد، یک راه حل آسان برای یک مسئلهٔ پیچیده، لزوماً یک راه حل ساده برای مسایل کاهش یافته به آن ایجاد نمی‌کند. بنابراین، مفهوم مناسب، بستگی به کلاس پیچیدگی تحت مطالعه دارد. در هنگام مطالعهٔ کلاس پیچیدگی NP و کلاسهای مشکلتر از قبیل سلسله مراتب چندجمله‌ای، کاهشهای دارای زمان چندجمله‌ای استفاده می‌شوند. در هنگام مطالعهٔ کلاسهای بین P از قبیل NC و NL کاهشهای فضای لگاریتمی استفاده می‌شود. کاهشها هم چنین در نظریهٔ محاسبه‌پذیری برای انکه ببینیم آیا مسایل بوسیلهٔ ماشین حل می‌شوند یا نه استفاده می‌شوند. در این حالت، کاهشها فقط به توابع قابل محاسبه محدود می‌شوند. در مورد مسایل بهینه‌سازی، ما اغلب در قالب کاهش نگهداری تقریب فکر می‌کنیم. فرض کنید که ما دو مسئلهٔ بهینه‌سازی داریم، به‌طوری‌که نمونه‌های یک مسئله می‌توانند به نمونه‌های دیگری نگاشته شوند، به‌طوری‌که جوابهای تقریباً بهینه در نمونه‌های مسئلهٔ دوم می‌توانند برای بدست آوردن جوابهای بهینه برای اولی، به عقب برگردند. بدین طریق اگر ما یک الگوریتم بهینه‌سازی داشته باشیم که پاسخ‌های تقریباً بهینه برای نمونه‌های مسئلهٔ B را پیدا می‌کند و یک کاهش نگهداری تقریب کارا برای مسئلهٔ A به مسئله B را نیز بدست می‌دهد، با ترکیب آن‌ها یک الگوریتم بهینه‌سازی ایجاد می‌کنیم که پاسخ‌های تقریباً بهینه برای نمونه‌های مسئلهٔ A بدست می‌دهد. کاهشهای نگهداری تقریب، اغلب برای اثبات نتایج سختی تقریب استفاده می‌شوند. اگر تقریب یک مسئلهٔ بهینه‌سازی A در عاملی بهتر از α برای یک α سخت باشد و یک کاهش نگهداری تقریب β از مسئلهٔ A به مسئلهٔ B وجود داشته باشد، می‌توانیم نتیجه بگیریم که تقریب مسئلهٔ B در عامل α/β سخت است.

مثال‌ها

برای اینکه نشان دهیم مسئلهٔ تصمیم P تصمیم ناپذیر است، باید یک کاهش از یک مسئلهٔ تصمیم که تاکنون شناخته شده‌است، پیدا کنیم که برای P تصمیم ناپذیر است. این تابع تصمیم باید یک تابع قابل محاسبه باشد. به خصوص ما اغلب با نشان دادن اینکه مسئلهٔ توقف به P کاهش می‌یابد، نشان می‌دهیم که مسئلهٔ P تصمیم ناپذیر است. کلاسهای پیچیدگی P, NP و PSPACE تحت کاهشهای زمان چند جمله‌ای بسته هستند. کلاسهای پیچیدگی L, NL, P, NP و PSPACE تحت کاهش بسته هستند. مثال جزئی مثالی که متعاقباً می‌آید نشان می‌دهد که چگونه از کاهش از مسئلهٔ توقف برای اثبات اینکه یک زبان، تصمیم ناپذیر است استفاده کنیم. فرض کنید که (H(M, w مسئلهٔ تشخیص اینکه آیا یک ماشین تورینگ M در رشتهٔ ورودی w توقف می‌کند یا نه باشد. این زبان به عنوان یک زبان تصمیم ناپذیر شناخته می‌شود. فرض کنید (E(M مسئلهٔ تشخیص اینکه آیا زبان پذیرشهای یک ماشین تورینگ داده شده M تهی است یا نه می‌باشد. نشان می‌دهیم که E توسط کاهش از 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.