ان-پی کامل قوی
[۱]ان-پی کامل قوی
در نظریه ی پیچیدگی محاسباتی، ان-پی کامل قوی بودن یک ویژگی مسایل محاسباتی است که حالت خاصی از ان-پی کامل بودن است. یک مسئله ی محاسباتی، در حالت کلی می تواند پارامترهای عددی داشته باشد. برای مثال، ورودی در مسئله ی بارگذاری صندوق ها، فهرستی از اشیاء با اندازه های معین، و نیز صندوق هایی با اندازه های معین برای در بر گرفتن این اشیاء است- این اندازه ها، یعنی اندازه ی اشیاء و صندوق ها، پارامترهای عددی مسئله هستند.
به یک مسئله، ان-پی کامل قوی گفته می شود که اگر تمامی پارامترهای عددی آن به طور چندجمله ای با طول ورودی مرتبط باشند، مسئله به شکل اولیه باقی می ماند[۲]. به یک مسئله، ان-پی سخت قوی می گویند اگر یک مسئله ی ان-پی کامل قوی را بتوان به شکل چندجمله ای به آن کاهش داد؛ در بهینه سازی ترکیبی، به طور خاص، عبارت "ان-پی سخت قوی" به مسائلی اتلاق می شود که کاهش چندجمله ای از آنها به یک مسئله ی ان-پی کامل قوی یافت نشده باشد.
پارامترهای عددی یک مسئله معمولا به شکل دودویی داده می شوند، بنابراین مسئله ای با اندازه ی ورودی n می تواند پارامترهایی را شامل شود که اندازه شان توانی از n است. اگر مسئله را با پارامترهای ورودی به شکل یگانی بازتعریف کنیم، آنگاه پارامترها باید به اندازه ی ورودی محدود شوند. بنابراین، ان-پی کامل قوی بودن یا ان-پی سخت بودن می تواند بر اساس ان-پی کامل بودن یا ان-پی سخت بودن نسخه ی یگانی مسئله نیز باشد.
بطور مثال، مسئله یبارگذاری صندوق ها، یک مسئله ی ان-پی کامل قوی است در حالیکه مسئله ی کولی پشتی صفر و یک، تنها ان-پی کامل ضعیف است. بنابراین نسخه ای از مسئله ی بارگذاری صندوق ها که در آن اندازه ی اشیاء و صندوق ها اعداد صحیح محدود شده به یک چندجمله ای هستند، همچنان یک مسئله ی ان-پی کامل باقی می ماند، در حالیکه نسخه ی مشابه مسئله ی کوله پشتی را می توان با برنامه سازی پویا در زمان چندجمله ای حل کرد.
در حالیکه می توان برای ورودی های نسبتا کوچک، برای مسائل ان-پی کامل ضعیف، به طور عملی راه حال های کارآمد ارائه کرد اما برای مسائل ان-پی کامل قوی این امکان وجود ندارد. از رویکرد نظری، هر مسئله ی تقریب ان-پی سخت قوی با تابع حالت محدود به چندجمله ای نمی تواند شکل تقریبی چندجمله ای داشته باشد، مگر اینکه P=NP[۳]. با این وجود، معکوس آن نادرست است: به طور مثال، اگر P برابر NP نباشد، مسئله ی کوله پشتی با دو محدودیت ان-پی سخت قوی نیست، اما هیچ تابع حالت محدود به چندجمله ای ندارد حتی وقتی حالت بهینه محدود به چندجمله ای است. [۴].
ممکن است برخی مسائل ان-پی کامل قوی در حالت میانگین براحتی قابل حل باشند، اما به طور محتمل در عمل نمونه های دشواری پیش رو قرار خواهند گرفت. اگر P=NP نباشد، هیچ تابع حالت محدود به چندجمله ای کاملی برای مسائل مسائل ان-پی کامل قوی وجود نخواهد داشت.[۵]
منابع [ویرایش]
- ↑ http://en.wikipedia.org/wiki/Strongly_NP-complete
- ↑ Garey, M. R.; Johnson, D. S. (July 1978). "'Strong' NP-Completeness Results: Motivation, Examples, and Implications". Journal of the Association for Computing Machinery (ACM) 25 (3): 499–508. DOI:10.1145/322077.322090. ISSN 0004-5411. MR 478747. http://doi.acm.org/10.1145/322077.322090.
- ↑ Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. pp. 294–295. ISBN 3540653678. MR 1851303.
- ↑ H. Kellerer and U. Pferschy and D. Pisinger (2004). Knapsack Problems. Springer.
- ↑ Garey, M. R.; Johnson, D. S. (1979). Victor Klee. ed. Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. W. H. Freeman and Co.. pp. x+338. ISBN 0-7167-1045-5. MR 519066.
