NP-easy
پیچیدگی کے نظریہ میں، پیچیدگی کلاس این پی-ایزی فنکشن کے مسائل کا مجموعہ ہے جو این پی میں کسی فیصلے کے مسئلے کے لیے اوریکل کے ساتھ ایک تعیناتی ٹورنگ مشین کے ذریعے کثیر الجہتی وقت میں حل کیا جا سکتا ہے۔ دوسرے لفظوں میں، ایک مسئلہ X NP-آسان ہے اگر اور صرف اس صورت میں جب NP میں کوئی مسئلہ Y موجود ہو جیسے کہ X کثیر الجہتی وقت ٹورنگ Y سے قابل تخفیف ہو۔ اس کا مطلب یہ ہے کہ Y کے لیے اوریکل کو دیکھتے ہوئے، ایک الگورتھم موجود ہے جو X کو کثیر الجہتی وقت میں حل کرتا ہے (ممکنہ طور پر اس اوریکل کو بار بار استعمال کرکے)۔ این پی-ایزی ایف پی این پی کا دوسرا نام ہے (فنکشن مسئلہ مضمون دیکھیں) یا ایف ڈی 2 پی کے لیے (کثیر درجہ بندی مضمون دیکھیں)۔ این پی کے آسان مسئلے کی ایک مثال تاروں کی فہرست کو ترتیب دینے کا مسئلہ ہے۔ فیصلہ کا مسئلہ "سٹرنگ اے سٹرنگ بی سے بڑا ہے" این پی میں ہے۔ کوئکسورٹ جیسے الگورتھم ہیں جو موازنہ کے معمول کے مطابق کالوں کی صرف ایک کثیر تعداد کے علاوہ اضافی کام کی کثیر تعداد کا استعمال کرتے ہوئے فہرست کو ترتیب دے سکتے ہیں۔ اس لیے چھانٹنا این پی آسان ہے۔ مزید مشکل مسائل بھی ہیں جو این پی آسان ہیں۔ مثال کے لیے این پی مساوی دیکھیں۔ این پی-ایزی کی تعریف کئی ایک کمی کے بجائے ٹورنگ کمی کا استعمال کرتی ہے کیونکہ مسئلہ Y کے جوابات صرف سچ یا غلط ہیں، لیکن مسئلہ X کے جوابات زیادہ عام ہو سکتے ہیں۔ لہذا، ایک ہی جواب کے ساتھ X کی مثال کو Y کی مثال میں ترجمہ کرنے کا کوئی عمومی طریقہ نہیں ہے۔ حوالہ جات نوٹ کریں۔ پیچیدگی کلاسیں