ان‌پی سخت

نمودار اویلر برای مجموعه‌های P‏، NP‏، ان‌پی کامل، و NP-Hard. بخش چپِ نمودار معتبر است با این فرض که P ≠ NP، و بخش راستِ نمودار معتبر است با این فرض که P = NP.

مجموعهٔ «ان‌پی-سخت» (به انگلیسی: NP-hard) شامل چندهزار مسئلهٔ مختلف با کاربردهای فراوان است که تاکنون برای آن‌ها راه حل سریع و قابل انجام در زمان معقول پیدا نشده‌است و به احتمال زیاد در آینده نیز یافت نخواهد شد. این که راه حل سریعی برای آن‌ها وجود ندارد هم اثبات نشده‌است. البته ثابت شده‌است که اگر فقط برای یکی از این مسئله‌ها راه حل سریعی پیدا شود٫این راه حل موجب حل سریع بقیهٔ مسئله‌ها خواهد شد. البته احتمال پیدا شدن چنین الگوریتمی ضعیف است. منظور از راه حل سریع آن است که زمان اجرای آن با اندازهٔ ورودی مسئله به صورت چندجمله‌ای رابطه داشته باشد.

ان پی سخت (زمان چندجمله‌ای غیر قطعی سخت) در نظریه پیچیدگی محاسباتی یک کلاسی از مسائل است که "دست کم به سختی سخت‌ترین مسئله‌های NP" است. مسئلهٔ H یک مسئلهٔ ان پی سخت است اگر و فقط اگر یک مسئلهٔ ان پی کامل L که زمان چندجمله‌ای تورینگ تقلیل (polynomial time Turing-reducible) به سمت H وجود داشته باشد (L ≤ TH). به عبارت دیگر L می‌تواند در زمان چندجمله‌ای به وسیلهٔ دستگاه اوراکل با اوراکل H حل شود. به صورت غیررسمی می‌توانیم الگوریتمی در نظر بگیریم که می‌تواند مانند یک ماشین اوراکل به عنوان یک زیر روال برای حل H تماس بگیرد و L را در زمان چندجمله‌ای حل کند اگر فراخوانی زیرروال تنها یک گام برای محاسبه بگیرد. مسئلهٔ ان پی سخت می‌تواند به هر صورتی باشد: مسئله‌های تصمیم‌گیری، مسئله‌های جستجو یا مسئله‌های بهینه‌سازی..

تعاریف جایگزین

تعریف جایگزین ان پی سخت اغلب استفاده محدود ان پی سخت برای مسائل تصمیم‌گیری و سپس برای استفاده کاهش زمان چند جمله‌ای به چند به یک کاهش تورینگ است؛ بنابراین، زبان L ان پی سخت است اگر ∀L' ∈ NP, L' ≤ L. اگر همچنین این حالت که L در ان پی باشد بنابراین L ان پی کامل نامیده می‌شود.

ریشهٔ انگلیسی

ان پی-سخت: Non-deterministic Polynomial-time hard)→NP-hard)

• حل نشدنی در زمان چندجمله‌ای بر حسب اندازهٔ ورودی مسئله (زمان معقول)

کنوانسیون نام‌گذاری ان پی

سیستم نام‌گذاری خانواده ان پی گیج‌کننده‌است: مسائل ان پی سخت همه ان پی نیستند با وجود این که پسوند NP را در کلاس اسمی خود دارند. اگرچه نام هم‌اکنون در حال تثبیت است و بعید است تغییر کند. از طرف دیگر سیستم نام‌گذاری ان پی معنی عمیق‌تری دارد زیرا خانواده ان پی در ارتباط با کلاس ان پی تعریف شده‌اند:

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

در پی آمد این تعاریف داریم:

• مسئلهٔ H حداقل به سختی L است، زیرا H می‌تواند برای حل L مورد استفاده قرار گیرد. ;
• از آنجا که L ان پی کامل باشد و از این رو سخت‌ترین در کلاس ان پی است، همچنین مسئلهٔ H حداقل به اندازه ان پی سخت است اما H نباید در ان پی باشد و بنابراین نباید یک مسئله تصمیم‌گیری باشد (اگر هم یک مسئلهٔ تصمیم‌گیری بود نیاز ندارد در ان پی باشد). ;
• از آنجا که مسئلهٔ‌های ان پی کامل به وسیلهٔ کاهش زمان چندجمله‌ای به چند به یک (تبدیل چندجمله‌ای)، به همدیگر تبدیل می‌شوند، تمام مسئله‌های ان پی کامل می‌توانند در زمان چندجمله‌ای با کاهش H حل شوند؛ بنابراین تمام مسئله‌ها در ان پی به H کاهش پیدا می‌کند. توجه: اگرچه این درگیری‌ها دو تبدیل مختلف را ترکیب می‌کند: از مسئلهٔ تصمیم‌گیری ان پی کامل به مسئلهٔ ان پی کامل L به وسیلهٔ تبدیل چندجمله‌ای و از L به H به وسیلهٔ چندجمله‌ای کاهش تورینگ. ;
• اگر یک الگوریتم پند جمله‌ای برای هر مسئلهٔ ان پی سخت وجود داشته باشد، بنابراین الگوریتم‌هایی برای تمام مسئله‌ها در ان پی وجود دارند، از این رو P = NP. ;
• اگر P ≠ NP، بنابراین مسئله‌های ان پی سخت هیچ راه حلی در زمان چندجمله‌ای ندارند، تا زمانی‌که P = NP حل نمی‌شود خواه مسئله‌های ان پی سخت بتوانند در زمان چندجمله‌ای حل شوند. ;
• اگر یک مسئلهٔ بهینه‌سازی H دارای یک L نسخه تصمیم‌گیری ان پی کامل باشد، آنگاه H ان پی سخت است.

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

مفهوم و مقایسهٔ آن با ان پی-کامل

مسئلهٔ H ان پی-سخت است اگر و فقط اگر مسئلهٔ L از نوع ان پی-کامل موجود باشد، به‌طوری‌که زمان حل آن بر حسب چندجمله‌ای قابل کاهش به Hباشد: (L ≤ _TH)به عبارتی دیگر L را می‌توان در زمان زیاد با ماشین اوراکل H حل کرد. به‌طور غیررسمی ما می‌توانیم به الگوریتمی فکر کنیم که می‌تواندزیرروالی را برای حل H فراخوانی کند و L را در زمان زیاد حل کند اگر فراخوانی آن زیر روال فقط یک گام برای محاسبه طول بکشد. مسائل ان پی-سخت ممکن است از هر نوعی باشند:مسائل تصمیم گیری٫مسائل جستجو٫مسائل بهینه سازی. طبق روال تعریف: (توجه داشته باشید که این‌ها صرفاً ادعا هستند نه تعریف):

• مسئلهٔ H حداقل به سختی مسئلهٔ L است. چون H می‌تواند برای حل L استفاده شود.
• چون L ان پی-کامل است ٫بنابراین به سختی مسائل نوع ان پی است. مسئلهٔ H حداقل به سختی مسئلهٔ ان پی است. اما H نباید ان پی باشد و بنابراین نباید از نوع مسائل تصمیم گیری باشد(حتی اگر از نوع مسایل تصمیم‌گیری باشد نیازی ندارد ازنوع مسائل ان پی باشد.)
• مسائل ان پی-کامل با زمان زیاد با ۱ واحد کاهش به یکدیگر تبدیل می‌شوند(همچنین تحولات چند جمله‌ای نیز نامیده می‌شوند.)

همهٔ مسائل ان پی-کامل با کاهش H می‌توانند در زمان زیاد حل شوند. بنابراین همهٔ مسائل در ان پی قابل کاهش به H هستند. توجه داشته باشید هر چند این شامل ترکیب کردن ۲ تبدیل است:

1. از ان پی-کامل:مسائل تصمیم گیری به مسائل ان پی-کامل با تحولات چندجمله‌ای
2. از L به H با کاهش چند جمله‌ای تورینگ. ماشین تورینگ

• اگر یک الگوریتم چندجمله‌ای برای هر مسئلهٔ ان پی-سخت موجود باشد٫ سپس الگوریتمهای چندجمله‌ای برای همهٔ مسائل در ان پی وجود دارند و بنابراین مسئله برابری پی و ان‌پی
• اگر P ≠ NP باشد ٫ مسائل ان پی-سخت راه حلی در زمان‌های زیاد ندارند. زمانی که مسئله برابری پی و ان‌پی باشد ٫ مسائل حل نمی‌شوند. حتی اگر مسائل ان پی-سخت بتوانند در زمان زیاد حل شوند.
• اگر مسائل بهینه سازی ٫H یک نسخهٔ تصمیم‌گیری ان پی-کامل داشته باشند٫ H یک ان پی-سخت است.
• یک اشتباه رایج این است که فکر می‌کنیم ان پی در ان پی-سخت بر پایهٔ غیر چند جمله‌ای است. اگر چه به‌طور گسترده انتظار میرود که هیچ الگوریتم غیر چند جمله‌ای بر حسب تابع زمانی برای مسائل ان پی- سخت وجود ندارد ولی این موضوع هنوز اثبات نشده‌است. علاوه بر این مسائل از نوع ان پی همچنین شامل همهٔ مسائلی هستند که می‌توانند در چندجمله‌ای از تابع زمان حل شوند.

روش حل مسایل ان پی-سخت

روش‌های مختلفی برای حل سریع ولی نزدیک به بهینه برای یک مسئلهٔ ان پی-سخت وجود دارد:

• راه حل تقریبی قابل اثبات(الگوریتم‌های تقریبی):که در آن یک الگوریتم سریع برای حل مسئله ارائه می‌شود ولی اثبات می‌شود که اندازهٔ خروجی ضریبی از اندازهٔ خروجی بهینهٔ مسئله‌است.
• الگوریتم‌های مکاشفه‌ای:با این که الگوریتم‌هایی سریع هستند و به صورت تقریبی جواب را به دست می‌آورند٫اما در مورد ضریب تقریب یا میزان خوبی الگوریتم اثباتی وجود ندارد. بسیاری از این الگوریتم‌ها به صورت تجربی آزمایش می‌شوند. برخی از این الگوریتم‌ها از «روش حریصانه» برای حل استفاده می‌کنند.

الگوریتم‌ها

راه‌های معمول مقابله با چنین مسائلی عبارتند از:

• طراحی الگوریتم‌هایی برای پیدا کردن جواب‌های دقیق که استفاده از آن‌ها فقط برای مسائل با اندازه کوچک صورت می‌گیرد.
• استفاده از «الگوریتم‌های مکاشفه‌ای»(Heuristic) که جواب‌هایی به‌دست می‌دهد که احتمالاً درست هستند.
• پیدا کردن زیرمسئله‌هایی از مسئله یعنی تقسیم مسئله به مسئله‌های کوچکتر تا بشود از الگوریتم‌های مکاشفه‌ای بهتر و دقیق‌تری استفاده کرد.

نمونه مسائل ان پی-سخت

• مسئله فروشنده دوره‌گرد
• مسیر همیلتونی
• مسئله بزرگترین خوشه (پیدا کردن بزرگترین زیرگراف کامل) (maximum clique problem)

مثال‌ها

"با توجه به فواصل بین هر دو نقطه، کوتاه ترین مسیری که یک فروشنده می تواند از نقطه A، با بازدید از تمام نقاط، و بازگشت به نقطه A طی کند، چیست؟ این مسئله فروشنده دوره‌گرد است، یک مسئله NP-Hard در ریاضیات.

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

مسائل تصمیم‌گیری ای هستند که ان پی سخت هستند اما ان پی کامل نیستند، برای مثال مسئله توقف. این مسئله ایست که می‌پرسد «با توجه به یک برنامه و ورودی، آیا همیشه اجرا خواهد شد؟». این یک سؤال بله/خیر است، بنابراین یک مسئله تصمیم‌گیری است. ثابت کردن که مسئلهٔ توقف ان پی سخت است اما نه ان پی کامل آسان است. برای مثال مسئله بولی قابل راضی کردنی می‌تواند به وسیلهٔ تبدیل آن به توضیحات ماشین تورینگ که برای تخصیص تمام داده‌های درست تلاش می‌کند و زمانی که یکی را پیدا کند که فرمول را به توقف قانع کند و درغیراینصورت به یک حلقه بی‌نهایت می‌رود، به مسئله توقف کاهش پیدا کند. همچنین به راحتی می‌توان دید که مسئله توقف ان پی نیست از آنجا که تمام مسائل در ان پی در تعداد دستورالعمل‌های محدود قابل تصمیم‌گیری هستند، درصورتی‌که مسئله توقف به‌طور کلی این‌طور نیست. مسئله‌های ان پی سختی هم وجود دارند که نه ان پی کامل هستند نه تصمیم ناپذیر. برای مثال زبان فرمول بولی اندازه‌گیری درست (True quantified Boolean formulas) در فضای چندجمله‌ای قابل تصمیم پذیر است اما غیر قطعی نشده زمان چندجمله‌ای است (مگر اینکه NP = PSPACE).

جستارهای وابسته

• نظریه پیچیدگی محاسباتی
• پیچیدگی زمانی
• طراحی الگوریتم
• مهندسی الگوریتم
• P (پیچیدگی)
• NP (پیچیدگی)
• الگوریتم ان‌پی-آسان
• ان‌پی کامل
• ان-پی کامل قوی
• مسئله P در مقابل NP

منابع

• Reilly, E.D. (2004). Concise Encyclopedia of Computer Science. Wiley. ISBN 978-0-470-09095-4. Retrieved 2023-01-07.

• Garey, Michael R.; Johnson, David S. (1979). Computers and intractability : a guide to the theory of NP-completeness. San Francisco: W.H. Freeman. ISBN 0-7167-1044-7. OCLC 4195125.