. متن داده‌شده را خلاصه کن

متن: تعریف جایگزین ان پی سخت اغلب استفاده محدود ان پی سخت برای مسائل تصمیم‌گیری و سپس برای استفاده کاهش زمان چیند جمله‌ای به چند به یک کاهش تورینگ است؛ بنابراین، زبان 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 ان پی سخت است. یک اشتباه معمول این است که فکر کنیم که ان پی در ان پی سخت مخفف غیر چندجمله‌ای است. هر چند که به‌طور گسترده‌ای مشکوک است که هیچ الگوریتم …
خلاصه:
مجموعهٔ « ان‌پی-سخت » شامل چندهزار مسئلهٔ مختلف با کاربردهای فراوان است که تاکنون برای آن‌ها راه حل سریع و قابل انجام در زمان معقول پیدا نشده‌است و به احتمال زیاد در آینده نیز یافت نخواهد شد . این که راه حل سریعی برای آن‌ها وجود ندارد هم اثبات نشده‌است . البته ثابت شده‌است که اگر فقط برای یکی از این مسئله‌ها راه حل سریعی پیدا شود٫این راه حل موجب حل سریع بقیهٔ مسئله‌ها خواهد شد . البته احتمال پیدا شدن چنین الگوریتمی ضعیف است . منظور از راه حل سریع آن است که زمان اجرای آن با اندازهٔ ورودی مسئله به صورت چندجمله‌ای رابطه داشته باشد .