From Wikipedia, the free encyclopedia
مجموعهٔ «انپی-سخت» (به انگلیسی: 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 ≤ TH)به عبارتی دیگر L را میتوان در زمان زیاد با ماشین اوراکل H حل کرد. بهطور غیررسمی ما میتوانیم به الگوریتمی فکر کنیم که میتواندزیرروالی را برای حل H فراخوانی کند و L را در زمان زیاد حل کند اگر فراخوانی آن زیر روال فقط یک گام برای محاسبه طول بکشد. مسائل ان پی-سخت ممکن است از هر نوعی باشند:مسائل تصمیم گیری٫مسائل جستجو٫مسائل بهینه سازی. طبق روال تعریف: (توجه داشته باشید که اینها صرفاً ادعا هستند نه تعریف):
همهٔ مسائل ان پی-کامل با کاهش H میتوانند در زمان زیاد حل شوند. بنابراین همهٔ مسائل در ان پی قابل کاهش به H هستند. توجه داشته باشید هر چند این شامل ترکیب کردن ۲ تبدیل است:
روشهای مختلفی برای حل سریع ولی نزدیک به بهینه برای یک مسئلهٔ ان پی-سخت وجود دارد:
راههای معمول مقابله با چنین مسائلی عبارتند از:
مثالی از مسئله ان پی سخت در تصمیمگیری مسئله جمع زیرمجموعهاست که به این صورت است: با توجه به مجموعهای از اعداد صحیح، هیچ زیر مجموعه غیر تهی از آنها به صفر اضافه میشود؟ این یک مسئلهٔ تصمیمگیری است، و برای ان پی کامل اتفاق میافتد. مثال دیگر ان پی سخت مسئله بهینهسازی پیدا کردن حداقل هزینه مسیر چرخهای از طریق تمام گرهها از یک گراف وزندار است که به عنوان مسئله فروشنده دوره گرد شناخته شدهاست.
مسائل تصمیمگیری ای هستند که ان پی سخت هستند اما ان پی کامل نیستند، برای مثال مسئله توقف. این مسئله ایست که میپرسد «با توجه به یک برنامه و ورودی، آیا همیشه اجرا خواهد شد؟». این یک سؤال بله/خیر است، بنابراین یک مسئله تصمیمگیری است. ثابت کردن که مسئلهٔ توقف ان پی سخت است اما نه ان پی کامل آسان است. برای مثال مسئله بولی قابل راضی کردنی میتواند به وسیلهٔ تبدیل آن به توضیحات ماشین تورینگ که برای تخصیص تمام دادههای درست تلاش میکند و زمانی که یکی را پیدا کند که فرمول را به توقف قانع کند و درغیراینصورت به یک حلقه بینهایت میرود، به مسئله توقف کاهش پیدا کند. همچنین به راحتی میتوان دید که مسئله توقف ان پی نیست از آنجا که تمام مسائل در ان پی در تعداد دستورالعملهای محدود قابل تصمیمگیری هستند، درصورتیکه مسئله توقف بهطور کلی اینطور نیست. مسئلههای ان پی سختی هم وجود دارند که نه ان پی کامل هستند نه تصمیم ناپذیر. برای مثال زبان فرمول بولی اندازهگیری درست (True quantified Boolean formulas) در فضای چندجملهای قابل تصمیم پذیر است اما غیر قطعی نشده زمان چندجملهای است (مگر اینکه NP = PSPACE).
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.