الگوریتم ان‌پی-آسان

در نظریه پیچیدگی، کلاس پیچیدگی NP-آسان (به انگلیسی: NP-easy)، مجموعه ای از مسائل تابع است که که قابل حل در زمان چندجمله‌ای توسط یک ماشین تورینگ قطعی با اوراکل برای تصمیم‌گیری برخی مسائل در NP هستند. به عبارت دیگر، یک مسئله NP , X-آسان است اگر و تنها اگر برخی از مسائل NP در Y وجود داشته باشد از جمله اینکه X زمان چندجمله‌ای تقلیل تورینگ به Y است. این بدین معناست که اواکل را برای Y می‌گیرد، یک الگوریتمی وجود دارد که X را در زمان چندجمله‌ای حل می‌کند.

- آسان نام دیگری برایFP^NP است (به مقاله مشکل تابع نگاه کنید) یا برای FΔ2P (به مقاله سلسله مراتب چندجمله‌ای نگاه کنید). یک مثال از مشکل NP-آسان، مشکل مرتب‌سازی یک لیست از رشته‌ها است. مشکل تصمیم‌گیری در NP این است که " آیا رشتهٔ A از رشتهٔ B بیشتر است. الگوریتم‌هایی مانند مرتب‌سازی سریع وجود دارند که می‌تواند لیست را با استفاده از فقط یک تعداد چندجمله‌ای از فراخوانی معمول به مقایسه، مرتب کند، به اضافهٔ مقدار چندجمله‌ای از کار اضافی؛ بنابراین مرتب‌سازی NP-آسان هست. همچنین مشکلات سختری وجود دارد که NP-آسان هستند. برای مثال به NP-معادل نگاه کنید. تعریف NP –آسان به جای کاهش بیش از یکی، از کاهش ترینگ استفاده می‌کند زیرا پاسخ مسئله Y یا درست یا نادرست است، اما پاسخ به X می‌تواند کلی تر باشد؛ بنابراین، هیچ راه کلی برای ترجمه یک نمونه از X به یک نمونه از Y با همان جواب وجود ندارد.

جستارهای وابسته

• نظریه پیچیدگی محاسباتی
• پیچیدگی زمانی
• طراحی الگوریتم
• مهندسی الگوریتم
• P (پیچیدگی)
• NP (پیچیدگی)
• ان‌پی سخت
• ان‌پی کامل
• ان-پی کامل قوی
• مسئله P در مقابل NP

منابع

• Garey, Michael R. ; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5.