موضوع مقاله: کاهش پیچیدگی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # کاهش پیچیدگی | مقدمه: کاهش (پیچیدگی) در نظریهٔ محاسبات و نظریهٔ پیچیدگی محاسباتی، کاهش، الگوریتمی برای انتقال یک مسئله به مسئلهٔ دیگری می‌باشد. | ## بخش 1: کاهش پیچیدگی | کاهش از یک مسئله به مسئلهٔ دیگر ممکن است برای نشان دادن اینکه مسئلهٔ دوم حداقل به اندازهٔ مسئلهٔ اول، سخت است استفاده شود. ساختار ریاضی ایجاد شده درمجموعه‌ای از مسائل با کاهش یک نوع خاص، عموماً یک مرتبهٔ پایین‌تر را تشکیل می‌دهد که کلاسهای هم‌ارزی آن ممکن است برای تعریف درجهٔ غیرقابل حل بودن و کلاسهای پیچیدگی استفاده شود. به‌طور شهودی، مسئلهٔ A قابل کاهش به مسئلهٔ B است اگر الگوریتم کارای حل مسئله ی B بتواند به عنوان یک زیر روال برای حل کارای مسئلهٔ A نیز استفاده شود. ما معمولاً A ≤m B را با زیروندی در ≤ می‌نویسیم که نوع کاهش استفاده شده را نشان دهیم (m:کاهش نگاشت، p : کاهش چندجمله‌ای) مقدمه ما اغلب در حال تلاش برای حل مسائلی هستیم که شبیه به مسائلی که تاکنون حل کرده‌ایم می‌باشند. در این موارد، اغلب یک راه سریع حل مسئلهٔ جدید ، انتقال هر نمونهٔ مسئلهٔ جدید به نمونه‌هایی از مسئلهٔ قدیمی است، و آن‌ها را با راه حلهای موجود حل می‌کنیم و سپس از آن‌ها برای بدست آوردن راه حل نهایی استفاده می‌کنیم. یک استفادهٔ ماهرانه تر این است: فرض کنید که مسئله‌ای داریم که می‌دانیم حل کردن آن سخت است، و یک مسئلهٔ جدید مشابه داریم. آنگاه، اگر نشان دهیم که هر نمونه از مسئلهٔ قدیمی می‌تواند به راحتی با انتقال به نمونه‌هایی از مسئله‌های جدید حل شود، و آن‌ها را حل کند، با یک تناقض رو به رو می‌شویم. ما می‌توانیم از این دانش که با فرمول زیر ترکیب شده‌است برای بدست آوردن ضرب هر دو عدد استفاده کنیم: A*b= a+b)^2-a^2-b^2)/2 ما هم چنین در مسیر دیگر نیز یک کاهش داریم. به وضوح، اگر ما بتوانیم دو عدد را ضرب کنیم، ما می‌توانیم مربع یک عدد را بدست آوریم. اگرچه کاهش، سخت تر هم می‌شود اگر ما این محدودیت را که فقط یک بار می‌توانیم از تابع توان و آن هم فقط در پایان استفاده کنیم، نیز اضافه شود. در این حالت حتی اگر ما مجاز به استفاده از همهٔ عملیات حسابی پایه‌ای، شامل ضرب، باشیم، در کل هیچ کاهشی وجود ندارد. از آنجا که ما ممکن است مجبور به محاسبهٔ یک عدد گنگ مانند از اعداد گویا باشیم، با رفتن به جهت دیگر ما می‌توانیم یک عدد را فقط با یک بار استفاده از ضرب، آن هم در انتها، به توان ۲ برسانیم. با استفاده از این شکل محدود کاهش، ما نتیجه‌ای که چندان هم تعجب‌آور نیست را نشان داده‌ایم، یعنی اینکه ضرب به‌طور کلی نسبت به مربع کردن سخت تر است. | ## بخش 2: کاهش پیچیدگی | ویژگی‌ها یک کاهش، یک رابطه‌ی شبه ترتیب است که به عنوان یک رابطهٔ بازتابی و متعدی در (P(N)×P(N تعریف می‌شود و در آن (P(N یک مجموعهٔ توانی از اعداد طبیعی است. انواع و کاربردهای کاهش همانطور که در مثال بالا توصیف شد، دو نوع اصلی کاهش وجود دارد که در پیچیدگی محاسباتی استفاده می‌شود، کاهش چند به یک و کاهش چرخشی. کاهشهای چرخشی، جواب یک مسئله را محاسبه می‌کند و فرض می‌کند که حل مسئلهٔ دیگر آسان است. کاهش چند به یک، قویتر از کاهش چرخشی است و در هنگام جداسازی مسایل به کلاسهای پیچیدگی متفاوت، کاراتر است. یک مسئله برای یک کلاس پیچیدگی کامل است اگر که هر مسئله در کلاس به آن مسئله کاهش یابد و خود آن نیز در کلاس باشد. در این کار، مسئله، کلاس را نشان می‌دهد، از آنجا که راه حل آن می‌تواند در ترکیب با کاهشها، برای حل هر مسئله در کلاس استفاده شود. به‌طور مثال، کاملاً ممکن است که یک مسئلهٔ NP-complete مانند مسئلهٔ رضایت بخشی بولی که حل آن مشکل است را به یک مسئلهٔ بدیهی مانند تشخیص اینکه آیا آن عدد مساوی صفر است، با داشتن ماشین کاهش که مسئله را اگر جواب داشته باشد در زمان توانی حل می‌کند و خروجی صفر را می‌دهد تبدیل کنیم. اگرچه، این چیز زیادی حاصل نمی‌کند، زیرا با اینکه ما می‌توانیم مسئلهٔ جدید را حل کنیم، اجرای کاهش، به اندازهٔ حل مسئلهٔ قدیمی سخت است. به‌طور مشابه، کاهشی که یک تابع غیرقابل محاسبه را محاسبه می‌کند می‌تواند یک مسئلهٔ تصمیم ناپذیر را به مسئلهٔ تصمیم پذیر تبدیل کند. همانطور که مایکل سیپسردر مقدمه‌ای بر نظریه محاسبه، اشاره می‌کند، اگر محاسبهٔ خود کاهش مشکل بود، کاهش باید نسبت به پیچیدگی مسائل معمولی در کلاس [...]، ساده باشد، یک راه حل آسان برای یک مسئلهٔ پیچیده، لزوماً یک راه حل ساده برای مسایل کاهش یافته به آن ایجاد نمی‌کند. در هنگام مطالعهٔ کلاس پیچیدگی NP و کلاسهای مشکلتر از قبیل سلسله مراتب چندجمله‌ای، کاهشهای دارای زمان چندجمله‌ای استفاده می‌شوند. در هنگام مطالعهٔ کلاسهای بین P از قبیل NC و NL کاهشهای فضای لگاریتمی استفاده می‌شود. کاهشها هم چنین در نظریهٔ محاسبه‌پذیری برای انکه ببینیم آیا مسایل بوسیلهٔ ماشین حل می‌شوند یا نه استفاده می‌شوند. | ## بخش 3: کاهش پیچیدگی | فرض کنید که ما دو مسئلهٔ بهینه‌سازی داریم، به‌طوری‌که نمونه‌های یک مسئله می‌توانند به نمونه‌های دیگری نگاشته شوند، به‌طوری‌که جوابهای تقریباً بهینه در نمونه‌های مسئلهٔ دوم می‌توانند برای بدست آوردن جوابهای بهینه برای اولی، به عقب برگردند. بدین طریق اگر ما یک الگوریتم بهینه‌سازی داشته باشیم که پاسخ‌های تقریباً بهینه برای نمونه‌های مسئلهٔ B را پیدا می‌کند و یک کاهش نگهداری تقریب کارا برای مسئلهٔ A به مسئله B را نیز بدست می‌دهد، با ترکیب آن‌ها یک الگوریتم بهینه‌سازی ایجاد می‌کنیم که پاسخ‌های تقریباً بهینه برای نمونه‌های مسئلهٔ A بدست می‌دهد. اگر تقریب یک مسئلهٔ بهینه‌سازی A در عاملی بهتر از α برای یک α سخت باشد و یک کاهش نگهداری تقریب β از مسئلهٔ A به مسئلهٔ B وجود داشته باشد، می‌توانیم نتیجه بگیریم که تقریب مسئلهٔ B در عامل α/β سخت است. مثال‌ها برای اینکه نشان دهیم مسئلهٔ تصمیم P تصمیم ناپذیر است، باید یک کاهش از یک مسئلهٔ تصمیم که تاکنون شناخته شده‌است، پیدا کنیم که برای P تصمیم ناپذیر است. به خصوص ما اغلب با نشان دادن اینکه مسئلهٔ توقف به P کاهش می‌یابد، نشان می‌دهیم که مسئلهٔ P تصمیم ناپذیر است. مثال جزئی مثالی که متعاقباً می‌آید نشان می‌دهد که چگونه از کاهش از مسئلهٔ توقف برای اثبات اینکه یک زبان، تصمیم ناپذیر است استفاده کنیم. فرض کنید که (H(M, w مسئلهٔ تشخیص اینکه آیا یک ماشین تورینگ M در رشتهٔ ورودی w توقف می‌کند یا نه باشد. فرض کنید (E(M مسئلهٔ تشخیص اینکه آیا زبان پذیرشهای یک ماشین تورینگ داده شده M تهی است یا نه می‌باشد. اگر ورودی 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 تولید کنیم.