NP-equivalent
کمپیوٹیشنل پیچیدگی کے نظریہ میں، پیچیدگی کلاس این پی مساوی فنکشن کے مسائل کا مجموعہ ہے جو این پی آسان اور این پی سخت دونوں ہیں۔ این پی مساوی فنکشن کے مسائل کے لیے این پی مکمل کا ینالاگ ہے۔ مثال کے طور پر، مسئلہ فائنڈ-ایس یو بی ایس ای ٹی-ایس یو ایم این پی کے مساوی میں ہے۔ انٹیجرز کے ایک سیٹ کو دیکھتے ہوئے، فائنڈ-ایس یو بی ایس ای ٹی-ایس یو ایم انٹیجرز کے کچھ غیر خالی ذیلی سیٹ کو تلاش کرنے کا مسئلہ ہے جو صفر تک کا اضافہ کرتا ہے (یا اگر ایسا کوئی ذیلی سیٹ نہیں ہے تو خالی سیٹ کو واپس کرنا)۔ یہ اصلاح کا مسئلہ فیصلہ کے مسئلے سبسیٹ-سم سے ملتا جلتا ہے۔ انٹیجرز کے ایک سیٹ کو دیکھتے ہوئے، سبسیٹ-سم یہ تلاش کرنے کا مسئلہ ہے کہ آیا کوئی ذیلی سیٹ موجود ہے جس کا خلاصہ صفر ہے۔ سبسیٹ-سم این پی مکمل ہے۔ یہ ظاہر کرنے کے لیے کہ فائنڈ-ایس یو بی ایس ای ٹی-ایس یو ایم این پی کے مساوی ہے، ہمیں یہ ظاہر کرنا چاہیے کہ یہ این پی ہارڈ اور این پی آسان دونوں ہے۔ واضح طور پر یہ این پی سخت ہے۔ اگر ہمارے پاس ایک بلیک باکس ہوتا جس نے یونٹ ٹائم میں فائنڈ-سبسیٹ-سم کو حل کیا ہوتا، تو سبسیٹ-سم کو حل کرنا آسان ہوتا۔ بس بلیک باکس سے اس سب سیٹ کو تلاش کرنے کے لیے کہیں جس کا مجموعہ صفر ہو، پھر چیک کریں کہ آیا اس نے نان ایمپٹی سیٹ واپس کیا ہے۔ یہ این پی آسان بھی ہے۔ اگر ہمارے پاس ایک بلیک باکس ہوتا جس نے یونٹ ٹائم میں سبسیٹ-سم کو حل کیا ہوتا، تو ہم اسے فائنڈ-سبسیٹ-سم کو حل کرنے کے لیے استعمال کر سکتے تھے۔ اگر یہ غلط آتا ہے، تو ہم فوری طور پر خالی سیٹ واپس کر دیتے ہیں۔ بصورت دیگر، ہم ہر عنصر کو ترتیب میں دیکھتے ہیں اور اسے ہٹا دیتے ہیں بشرطیکہ سبسیٹ-سم اسے ہٹانے کے بعد بھی درست ہو جائے۔ ایک بار جب ہم ہر عنصر کا دورہ کر لیتے ہیں، تو ہم جواب کو سچ سے غلط میں تبدیل کیے بغیر کسی بھی عنصر کو ہٹانے کے قابل نہیں ہوں گے۔ اس وقت اصل عناصر کے بقیہ ذیلی سیٹ کا مجموعہ صفر ہونا چاہیے۔ اس کے لیے ہمیں یہ نوٹ کرنے کی ضرورت ہے کہ عناصر کو بعد میں ہٹانے سے یہ حقیقت تبدیل نہیں ہوتی کہ پہلے والے عنصر کو ہٹانے سے جواب درست سے غلط میں بدل گیا۔ سڈوکوڈ میں: فنکشن FIND-SUVSET-SUM (سیٹ S) اگر نہیں تو (SABSET-SUM (S)) S میں ہر x کے لیے {} واپس کرتا ہے اگر SABSET-SM (S-{x}) S: = S-{x} واپسی S ایک اور معروف NP-مساوی مسئلہ ٹریولنگ سیلز مین کا مسئلہ ہے۔ وضاحت اس تناظر میں این پی کا مطلب غیر متعین کثیر الجہتی وقت ہے۔ بولین افعال کی این پی مساوات کی کلاسیں بھی ہیں، جہاں این پی کا مطلب نفی اور ترتیب ہے۔ حوالہ جات نوٹ کریں۔ پیچیدگی کلاسیں