ان‌پی-سخت

Euler diagram for P, NP, ان‌پی کامل, and NP-hard set of problems

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

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

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

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

مثال‌ها

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

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

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

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

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

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

ان پی سخت

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

ان پی کامل

این‌ها سختترین مسائل در ان پی هستند. مثل مساله‌ای که ان پی سخت، در ان پی است.

ان پی آسان

حداکثر به سختی ان پی است اما بزوما ان پی نیست. از آنجایی که آنها ممکن است مشکلات تصمیم گیری نباشند.

ان پی معادل

دقیقا به سختی سختترین مسائل در ان پی است اما لزوما ان پی نیست.

References

• Michael R. Garey and David S. Johnson (1979). [۱] Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. 

ان‌پی سخت