ان‌پی سخت: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
Yamaha5Bot (بحث | مشارکتها) جز ←مفهوم و مقایسهٔ آن با ان پی-کامل: تمیزکاری با استفاده از AWB |
Luckie Luke (بحث | مشارکتها) انتقال از ان‌پی-سخت، برچسب تمیزکاری |
||
خط ۱:
{{تمیزکاری}}
[[پرونده:P np np-complete np-hard.svg|بندانگشتی|300px|چپ|نمودار اویلر برای مجموعه‌های [[کلاس پی|P]]، [[ان پی (کامل)|NP]]، [[ان‌پی کامل]]، و [[NP-Hard]]. بخش چپِ نمودار معتبر است با این فرض که P ≠ NP، و بخش راستِ نمودار معتبر است با این فرض که P = NP.]]
مجموعهٔ «'''ان‌پی-سخت'''» شامل چندهزار مسئلهٔ مختلف با کاربردهای فراوان است که تاکنون برای آن‌ها راه حل سریع و قابل انجام در زمان معقول پیدا نشده‌است و به احتمال زیاد در آینده نیز یافت نخواهد شد. این که راه حل سریعی برای آن‌ها وجود ندارد هم اثبات نشده‌است. البته ثابت شده‌است که اگر فقط برای یکی از این مسئله‌ها راه حل سریعی پیدا شود٫این راه حل موجب حل سریع بقیهٔ مسئله‌ها خواهد شد. البته احتمال پیدا شدن چنین الگوریتمی ضعیف است. منظور از راه حل سریع آن است که زمان اجرای آن با اندازهٔ ورودی مسئله به صورت [[چندجمله‌ای]] رابطه داشته باشد.
'''ان پی سخت''' (زمان چندجمله‌ای غیر قطعی سخت) در [[نظریه پیچیدگی محاسباتی]] یک کلاسی از مسائل است که "دست کم به سختی سختترین مشکلات NP" است. مشکل H یک ان پی سخت است اگر و فقط اگر یک مشکل ان پی کامل L که زمان چندجمله‌ای تورینگ تقلیل (polynomial time Turing-reducible) به سمت H وجود داشته باشد (L ≤ TH). به عبارت دیگر L می‌تواند در زمان چندجمله‌ای به وسیلهٔ دستگاه اوراکل با اوراکل H حل شود. به صورت غیررسمی می‌توانیم اگویتمی در نظر بگیریم که می‌تواند مانند یک ماشین اوراکل به عنوان یک زیر روال برای حل H تماس بگیرید و L را در زمان چندجمله‌ای حل کند اگر فراخوانی زیرروال تنها یک گام برای محاسبه بگیرد. مشکل ان پی سخت می‌تواند به هر صورتی باشد: مشکلات تصمیم‌گیری، مشکلات جستجو یا مشکلات بهینه‌سازی..
== تعاریف جایگزین ==
تعریف جایگزین ان پی سخت اغلب استفاده محدود ان پی سخت برای مسائل تصمیم‌گیری و سپس برای استفاده کاهش زمان چیند جمله‌ای به چند به یک کاهش تورینگ است؛ بنابراین، زبان L ان پی سخت است اگر ∀L' ∈ NP, L' ≤ L. اگر همچنین این حالت که L در ان پی باشد بنابراین L ان پی کامل نامیده می‌شود.
== ریشهٔ انگلیسی ==
'''ان پی-سخت:''' [[ویکی‌پدیا:NP (complexity)|Non-deterministic Polynomial-time]] hard)→[[ویکی‌پدیا:NP-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 از نوع [[ویکی‌پدیا:NP-complete|'''ان پی-کامل''']] موجود باشد، به‌طوری‌که زمان حل آن بر حسب [[چندجمله‌ای]] قابل کاهش به Hباشد: (L ≤ <sub>T</sub>H)به عبارتی دیگر L را می‌توان در زمان زیاد با ماشین [[ویکی‌پدیا:oracle|اوراکل]] H حل کرد. به‌طور غیررسمی ما می‌توانیم به الگوریتمی فکر کنیم که می‌تواندزیرروالی را برای حل H فراخوانی کند و L را در زمان زیاد حل کند اگر فراخوانی آن زیر روال فقط یک گام برای محاسبه طول بکشد.
سطر ۳۴ ⟵ ۶۰:
* [[مسئله فروشنده دوره‌گرد]]
* مسئله بزرگترین خوشه (پیدا کردن بزرگترین زیرگراف کامل) ([[:w:en:Maximum clique problem|maximum clique problem]])
== مثال‌ها ==
مثالی از مسئله ان پی سخت در تصمیم‌گیری مسئله جمع زیرمجموعه‌است که به این صورت است: با توجه به مجموعه‌ای از [[اعداد صحیح]]، هیچ زیر [[مجموعه غیر تهی]] از آن‌ها به صفر اضافه می‌شود؟ این یک مشکل تصمیم‌گیری است، و برای ان پی کامل اتفاق می‌افتد. مثال دیگر ان پی سخت [[مسئله بهینه‌سازی]] پیدا کردن حداقل هزینه مسیر چرخه‌ای از طریق تمام گره‌ها از یک گراف وزندار است که به عنوان مسئله [[فروشنده دوره گرد]] شناخته شده‌است.
مسائل تصمیم‌گیری ای هستند که ان پی سخت هستند اما ان پی کامل نیستند، برای مثال مسئله توقف. این مسئله ایست که می‌پرسد «با توجه به یک برنامه و ورودی، آیا همیشه اجرا خواهد شد؟». این یک سؤال بله/خیر است، بنابراین یک مسئله تصمیم‌گیری است. ثابت کردن که مشکل توقف ان پی سخت است اما نه ان پی کامل آسان است. برای مثال مسئله بولی قابل راضی کردنی می‌تواند به وسیلهٔ تبدیل آن به توضیحات [[ماشین تورینگ]] که برای تخصیص تمام داده‌های درست تلاش می‌کند و زمانی که یکی را پیدا کند که فرمول را به توقف قانع کند و درغیراینصورت به یک [[حلقه بی‌نهایت]] می‌رود، به [[مسئله توقف]] کاهش پیدا کند. همچنین به راحتی می‌توان دید که مسئله توقف ان پی نیست از آنجا که تمام مسائل در ان پی در تعداد دستورالعمل‌های محدود قابل تصمیم‌گیری هستند، درصورتی‌که مسئله توقف به‌طور کلی این‌طور نیست. مسئله‌های ان پی سختی هم وجود دارند که نه ان پی کامل هستند نه تصمیم ناپذیر. برای مثال زبان فرمول بولی [[اندازه‌گیری]] درست (True quantified Boolean formulas) در فضای چندجمله‌ای قابل تصمیم پذیر است اما غیر قطعی نشده زمان چندجمله‌ای است (مگر اینکه NP = PSPACE).
* [[نظریه پیچیدگی محاسباتی]]▼
== منابع ==
{{پانویس}}
* {{cite book|author = Edwin D. Reilly| year = ۲۰۰۴ | title = [http://books.google.ca/books?id=5Jaa1BVverIC&lpg=PA562&dq=Computers%20and%20Intractability:%20A%20Guide%20to%20the%20Theory%20of%20NP-Completeness&pg=PA560#v=onepage&q=Computers%20and%20Intractability:%20A%20Guide%20to%20the%20Theory%20of%20NP-Completeness&f=false] Concise encyclopedia of computer science | publisher = John Wiley and Sons Ltd | isbn =}}
== منابع ==
▲* [[نظریه پیچیدگی محاسباتی]]
* {{cite book|author = [[Michael R. Garey]] and [[David S. Johnson]] | year = ۱۹۷۹ | title = [http://www.amazon.com/dp/0716710455] [[Computers and Intractability: A Guide to the Theory of NP-Completeness]] | publisher = W.H. Freeman | isbn = ۰-۷۱۶۷-۱۰۴۵-۵}}
{{کلاس‌های پیچیدگی}}
| |||