ان‌پی سخت: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
Levin~fawiki (بحث | مشارکت‌ها) بدون خلاصۀ ویرایش |
Levin~fawiki (بحث | مشارکت‌ها) بدون خلاصۀ ویرایش |
||
خط ۳:
مجموعه ی «'''ان‌پی-سخت'''» شامل چندهزار مساله ی مختلف با کاربردهای فراوان است که تاکنون برای آن ها راه حل سریع و قابل انجام در زمان معقول پیدا نشده است و به احتمال زیاد در آینده نیز یافت نخواهد شد.این که راه حل سریعی برای آن ها وجود ندارد هم اثبات شده است.البته ثابت شده است که اگر فقط برای یکی از این مساله ها راه حل سریعی پیدا شود٫این راه حل موجب حل سریع بقیه ی مساله ها خواهد شد.البته احتمال پیدا شدن چنین الگوریتمی ضعیف است.منظور از راه حل سریع آن است که زمان اجرای آن با اندازه ی ورودی مساله به صورت [[چندجمله ای]] رابطه داشته باشد.
==ریشه ی انگلیسی ==
'''ان پی-سخت:'''[[
==نتالب==
یک مسالهٔ H
▲یک مسالهٔ H, NP سخت است اگر و فقط اگر مساله ی L از نوع NP کامل موجود باشد که چندجمله‌ای از تابع زمان قابل کاهش به Hاست.(L<=TH)
به عبارتی دیگر L را میتوان در زمان زیاد با ماشین اوراکلHحل کرد.به طور غیررسمی ما میتوانیم به الگوریتمی فکر کنیم که میتواند زیرروالی را برای حل Hفراخوانی کند و L را در زمان زیاد حل کند اگر فراخوانی آن زیر روال فقط یک گام برای محاسبه طول بکشد.
مسایل NP سخت ممکن است از هر نوعی باشند:
طبق روال تعریف: (توجه داشته باشید که اینها صرفا ادعا هستند نه تعریف):
*مسالهٔ Hحداقل به سختی مسالهٔ L است. چون Hمیتواند برای حلL استفاده شود.
سطر ۱۴ ⟵ ۱۳:
*چون مسایل NPکامل با زمان زیاد با ۱ کاهش به یکدیگر تبدیل میشوند(همچنین تحولات چند جمله‌ای نیز نامیده میشوند.)
همهٔ مسایل NP کامل با کاهش Hمیتوانند در زمان زیاد حل شوند.بنابراین همهٔ مسایل در NP کاهش به H هستند.توجه داشته باشید هر چند این شامل ترکیب کردن ۲تبدیل است:
از NPکامل:مسایل تصمیم گیری به مسایل NP کامل,با تحولات چندجمله‌ای و از LبهHبا کاهش چند جمله‌ای [[ماشین تورینگ|تورینگ]].
*اگر یک الگوریتم چندجمله‌ای برای هر مسالهٔ NPسخت موجود باشد,سپس الگوریتم‌های چندجمله‌ای برای همهٔ مسایل در NPوجود دارند و بنابراین [[P = NP]]
*اگر P!=NPپس مسایل NPسخت راه حلی در زمان‌های زیاد ندارند.زمانی که P=NPمسایل حل نمیشوند.حتی اگر مسایل NPسخت بتوانند در زمان زیاد حل شوند.
*اگر مسایل بهینه سازی H,یک نسخهٔ تصمیم گیری NPکامل داشته باشند.پس Hیک NPسخت است.
| |||