ان-پی کامل قوی

ان-پی کامل قوی
در نظریه ی پیچیدگی محاسباتی، ان-پی کامل قوی بودن یک ویژگی مسایل محاسباتی است که حالت خاصی از ان-پی کامل بودن است. یک مسئلهٔ محاسباتی، در حالت کلی می‌تواند پارامترهای عددی داشته باشد. برای مثال، ورودی در مسئلهٔ بارگذاری صندوق ها، فهرستی از اشیاء با اندازه‌های معین، و نیز صندوق‌هایی با اندازه‌های معین برای در برگرفتن این اشیاء است- این اندازه‌ها، یعنی اندازهٔ اشیاء و صندوق‌ها، پارامترهای عددی مسئله هستند.
به یک مسئله، ان-پی کامل قوی گفته می‌شود که اگر تمامی پارامترهای عددی آن به‌طور چندجمله ای با طول ورودی مرتبط باشند، مسئله به شکل اولیه باقی می‌ماند. به یک مسئله، ان-پی سخت قوی می‌گویند اگر یک مسئلهٔ ان-پی کامل قوی را بتوان به شکل چندجمله‌ای به آن کاهش داد؛ در بهینه‌سازی ترکیبی، به‌طور خاص، عبارت "ان-پی سخت قوی" به مسائلی اطلاق می‌شود که کاهش چندجمله‌ای از آن‌ها به یک مسئلهٔ ان-پی کامل قوی یافت نشده باشد.
پارامترهای عددی یک مسئله معمولاً به شکل دودویی داده می‌شوند، بنابراین مسئله‌ای با اندازهٔ ورودی n می‌تواند پارامترهایی را شامل شود که اندازه‌شان توانی از n است. اگر مسئله را با پارامترهای ورودی به شکل یگانی بازتعریف کنیم، آنگاه پارامترها باید به اندازهٔ ورودی محدود شوند. بنابراین، ان-پی کامل قوی بودن یا ان-پی سخت بودن می‌تواند بر اساس ان-پی کامل بودن یا ان-پی سخت بودن نسخهٔ یگانی مسئله نیز باشد.
بطور مثال، مسئله یبارگذاری صندوق ها، یک مسئلهٔ ان-پی کامل قوی است در حالیکه مسئلهٔ کولی پشتی صفر و یک، تنها ان-پی کامل ضعیف است. بنابراین نسخه‌ای از مسئلهٔ بارگذاری صندوق‌ها که در آن اندازهٔ اشیاء و صندوق‌ها اعداد صحیح محدود شده به یک چندجمله‌ای هستند، همچنان یک مسئلهٔ ان-پی کامل باقی می‌ماند، در حالیکه نسخهٔ مشابه مسئلهٔ کوله پشتی را می‌توان با برنامه‌سازی پویا در زمان چندجمله‌ای حل کرد.
در حالیکه می‌توان برای ورودی‌های نسبتاً کوچک، برای مسائل ان-پی کامل ضعیف، به‌طور عملی راه حال‌های کارآمد ارائه کرد اما برای مسائل ان-پی کامل قوی این امکان وجود ندارد. از رویکرد نظری، هر مسئلهٔ تقریب ان-پی سخت قوی با تابع حالت محدود به چندجمله ای نمی‌تواند شکل تقریبی چندجمله‌ای داشته باشد، مگر اینکه P=NP. با این وجود، معکوس آن نادرست است: به‌طور مثال، اگر P برابر NP نباشد، مسئلهٔ کوله پشتی با دو محدودیت ان-پی سخت قوی نیست، اما هیچ تابع حالت محدود به چندجمله ای ندارد حتی وقتی حالت بهینه محدود به چندجمله‌ای است. .
ممکن است برخی مسائل ان-پی کامل قوی در حالت میانگین به راحتی قابل حل باشند، اما به‌طور محتمل در عمل نمونه‌های دشواری پیش رو قرار خواهند گرفت. اگر P=NP نباشد، هیچ تابع حالت محدود به چندجمله‌ای کاملی برای مسائل مسائل ان-پی کامل قوی وجود نخواهد داشت.

منابع

↑ http://en.wikipedia.org/wiki/Strongly_NP-complete
↑ Garey, M. R.; Johnson, D. S. (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 0478747. ; ; ;
↑ 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 0519066. ;

[1] ttp://en.wikipedia.org/wiki/Strongly_NP-complete

[2] Garey, M. R.; Johnson, D. S. (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 0478747. ; ; ;

[vvv-3] Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. pp. 294–295. ISBN 3540653678. MR 1851303.

[4] H. Kellerer and U. Pferschy and D. Pisinger (2004). Knapsack Problems. Springer.

[5] 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 0519066. ;