NP (پیچیدگی)

در نظریه پیچیدگی محاسباتی NP که یکی از بنیادی‌ترین کلاس‌ها است. NP مخفف عبارت “non deterministic polynomial” است که به زمان اجرای آن اشاره دارد.
NP مجموعهٔ کلیه مسائل تصمیم‌گیری است که پیدا کردن جواب بله برای آن‌ها شامل اثبات ساده‌ای است که جواب حقیقتاً باید بله باشد. به‌طور دقیق تر این اثبات‌های ساده باید قابل بررسی در یک زمان اجرای چندجمله‌ای در یک ماشین تورینگ جبری باشد. در مقابل این تعریف NP مجموعه مسائل تصمیم‌گیری نامیده می‌شود که در یک زمان اجرای چندجمله‌ای در یک ماشین تورینگ غیر جبری قابل بررسی باشند. کلاس پیچیدگی P یکی از اعضای NP است اما NP شامل کلاس‌های مهم دیگری نیز هست؛ که پیچیده‌ترین آن‌ها NP-Complete است بطوریکه برای آن‌ها هیچ الگوریتم شناخته شده قابل اجرا در زمان چندجمله‌ای وجود ندارد.
مهمترین سؤالی که اکنون برای این کلاس‌ها در این نظریه وجود دارد این است که آیا P=NP؟ این سؤال می‌پرسد که آیا چنین الگوریتمی واقعاً برای مسائل NP-Complete و در کل NP وجود دارد یا خیر. این باور گسترده وجود دارد که این تساوی نمی‌تواند درست باشد.

## تعاریف رسمی
NP را می‌توان به وسیلهٔ NTIME نیز تعریف کرد:
 (NP=∪NTIME(n^k

## مقدمه
بسیاری از مسئله‌های معمول علوم کامپیوتر در حوزهٔ مسائل NP قرار دارند. مخصوصاً مدل تصمیم‌گیری بسیاری از مسائل جستجو و بهینه‌سازی در حوزهٔ NP قرار دارد.
نمونه‌هایی از زمینه‌هایی که شامل مسائل NP می‌شوند عبارتند از:
مانند جبر بولی، گراف، طراحی شبکه، زیست‌شناسی، فیزیک جدید، نظریه اعداد، نظریه بازی‌ها و پازل‌ها، نظریه زبان‌ها و ماشین‌ها و…

## تعریف بر پایهٔ بررسی کننده
به منظور تعریف این چنین NP بیایید مسئلهٔ مجموع زیر مجموعه‌ها را در نظر بگیرید. فرض کنید به ما تعدادی عدد صحیح داده شده‌است مثلاً {-۷و-۳و-۲ ۵و ۸و} و ما می‌خواهیم بدانیم که آیا مجموع اعضای یکی از زیر مجموعه‌های آن صفر می‌شود یا نه؟ در این مثال جواب بله‌است زیرا اعداد ۳,-۲٬۵ می‌توانند این شرط را بررسی کنند.

هنگامیکه مقدار اعداد صحیح ورودی زیاد شود تعداد زیر مجموعه‌ها به صورت توانی افزایش می‌یابد و در حقیقت مسئله فوق یک مسئله NP-Complete است.

در هر حال توجه شود که اگر به ما یک زیر مجموعه مشخص بدهند (بعضی اوقات گواه نامیده می‌شود) ما به راحتی می‌توانیم بررسی کنیم که آیا مجموع آن صفر است یا خیر. (تنها با جمع کردن اعضای آن زیر مجموعه) و اگر مجموع صفر باشد آن زیر مجموعه یک شاهد برای این است که جواب بله‌است. الگوریتمی که بررسی می‌کند آیادرزیر مجموعه داده شده مجموع اعضا صفر است بررسی‌کننده نامیده می‌شود.

**یک مسئله را عضو NP می‌نامند اگر و فقط اگر یک بررسی‌کننده برای آن وجود داشته باشد که در زمان اجرای
چندجمله‌ای اجرا شود. **

در مورد مسئله مجموع زیر مجموعه‌ها نیز بررسی‌کننده تنها نیازمند زمان اجرای خطی است که این دلیلی است برای اینکه این مسئله NP است.

توجه شود که در تعریف بر پایهٔ بررسی‌کننده NP نیازمند یک بررسی‌کننده به عنوان گواه برای جواب نه نیست. آن کلاس مسائلی که شامل یک شاهد این چنینی هستند CO-NP نامیده می‌شود. در حقیقت یک سؤال بدون جواب دیگری در اینجا وجود دارد که آیا تمام مسائل NP دارای یک گواه برای جواب نه هستند و در نتیجه CO-NP می‌شوند.

## تعریف ماشینی
معادل تعاریف قبلی این تعریف نیز وجود دارد که می‌گوید:
**NP مجموعه مسائل تصمیم‌گیری است که قابل حل شدن در یک زمان اجرای چندجمله‌ای در یک ماشین تورینگ غیر جبری می‌باشد.**

مثال
در اینجا یک لیست نا کامل از مسائل NP را بیان می‌کنیم:
تمام مسائل P (برای یک گواه مسئله P ما می‌توانیم کلاً گواه را نادیده بگیریم و مسئله را در زمان اجرای چندجمله‌ای حل کرد. همچنین توجه شود که یک ماشین تورینگ جبری یک ماشین تورینگ غیر جبری است که از هیچ‌کدام از توانایی‌های غیر جبری اش استفاده نمی‌کند.
مسئله پیدا کردن مقسوم علیه‌های یک عدد صحیح: دو عدد صحیح N و K داده شده‌اند. می‌خواهیم بدانیم آیا عدد صحیحی مثل F وجود دارد که ۱

مثال های دیگر:
* مسئله طولانی‌ترین مسیر
* بهینه‌سازی خطی عدد صحیح
* مسئلهٔ یافتن مجموعهٔ مستقل

## نتیجه‌گیری
مسائل NP در زمان نمایی با توجه به مقدار ورودی اجرا می‌شوند. واژه "NP کامل " بدین معنی است که یک مسئله ارزش این را ندارد که سعی شود به صورت بهینه کامل حل شود.

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

## منابع

* توماس اچ کورمن،  Charles E. Leiserson, رونالد ریوست،  and کلیفورد استین. *[[مقدمه‌ای بر الگوریتم‌ها]]*, Second Edition. MIT Press and McGraw-Hill, 2001. . Section 34.2: Polynomial-time verification, pp. &nbsp;979&ndash;983.
*  Sections 7.3&ndash;7.5 (The Class NP, NP-completeness, Additional NP-complete Problems), pp. &nbsp;241&ndash;271.
* David Harel, Yishai Feldman. Algorithmics: The Spirit of Computing, Addison-Wesley, Reading, MA, 3rd edition, 2004.
یاسر اسماعیل جامی

## پیوند به بیرون
* 
* Graph of NP-complete Problems
* American Scientist primer on traditional and recent complexity theory research: "Accidental Algorithms" 

رده:کلاس پیچیدگی