NP-hardness
کمپیوٹیشنل پیچیدگی کے نظریہ میں، این پی سختی (غیر متعین کثیر الجہتی وقت کی سختی) مسائل کی ایک کلاس کی وضاحتی خاصیت ہے جو غیر رسمی طور پر "کم از کم این پی میں سب سے مشکل مسائل کی طرح سخت" ہیں۔ این پی-ہارڈ مسئلہ کی ایک سادہ مثال سب سیٹ سم مسئلہ ہے۔ ایک زیادہ درست وضاحت یہ ہے کہ: ایک مسئلہ H NP-سخت ہوتا ہے جب NP میں ہر مسئلہ L کو کثیر الجہتی وقت میں H سے کم کیا جا سکتا ہے۔ یعنی، یہ فرض کرتے ہوئے کہ H کے حل میں 1 یونٹ وقت لگتا ہے، Hs حل کو کثیر الجہتی وقت میں L کو حل کرنے کے لیے استعمال کیا جا سکتا ہے۔ نتیجے کے طور پر، کسی بھی این پی-ہارڈ مسئلے کو حل کرنے کے لیے کثیر الجہتی ٹائم الگورتھم تلاش کرنے سے این پی میں تمام مسائل کے لیے کثیر الجہتی ٹائم الگورتھم ملے گا۔ جیسا کہ یہ شبہ ہے کہ P ष्णپ، اس بات کا امکان نہیں ہے کہ اس طرح کا الگورتھم موجود ہو۔ یہ شبہ ہے کہ این پی ہارڈ مسائل کے لیے کوئی کثیر الجہتی وقت کے الگورتھم موجود نہیں ہیں، لیکن یہ ثابت نہیں ہوا ہے۔ مزید برآں، کلاس P، جس میں تمام مسائل کو کثیر الجہتی وقت میں حل کیا جا سکتا ہے، NP کلاس میں موجود ہے۔ تعریف ایک فیصلہ مسئلہ H NP-سخت ہوتا ہے جب NP میں ہر مسئلے L کے لیے، L سے H تک کثیر الجہتی-وقت کئی-ایک کمی ہوتی ہے۔ ایک مساوی تعریف یہ ہے کہ NP میں ہر مسئلہ L کو کثیر الجہتی وقت میں حل کیا جا سکتا ہے۔ غیر رسمی طور پر، ایک الگورتھم کے بارے میں سوچا جا سکتا ہے جو ایسی اوریکل مشین کو H کو حل کرنے کے لیے ذیلی روٹین کے طور پر کال کرتا ہے اور کثیر الجہتی وقت میں L کو حل کرتا ہے اگر ذیلی روٹین کال کو حساب کرنے میں صرف ایک قدم لگتا ہے۔ ایک اور تعریف یہ ہے کہ این پی مکمل مسئلہ G سے H تک کثیر الجہتی وقت میں کمی کی ضرورت ہے۔ جیسا کہ NP میں کوئی بھی مسئلہ L کثیر الجہتی وقت میں G تک کم ہو جاتا ہے، L کثیر الجہتی وقت میں H تک کم ہو جاتا ہے لہذا یہ نئی تعریف پچھلے سے مراد ہے۔ یہ کلاس این پی-ہارڈ کو فیصلہ سازی کے مسائل تک محدود نہیں رکھتا، اور اس میں تلاش کے مسائل یا اصلاح کے مسائل بھی شامل ہیں۔ نتائج اگر P § NP، تو NP-سخت مسائل کو کثیر الجہتی وقت میں حل نہیں کیا جا سکتا۔ کچھ این پی ہارڈ آپٹیمائزیشن کے مسائل کثیر الجہتی وقت کے لگ بھگ کچھ مستقل تخمینہ تناسب (خاص طور پر، جو اے پی ایکس میں ہیں) یا یہاں تک کہ کسی بھی تخمینہ تناسب (جو پی ٹی اے ایس یا ایف پی ٹی اے ایس میں ہیں) تک ہو سکتے ہیں۔ مثالیں تمام این پی مکمل مسائل بھی این پی سخت ہیں (این پی مکمل مسائل کی فہرست دیکھیں)۔ مثال کے طور پر، وزن والے گراف کے تمام نوڈس کے ذریعے کم سے کم لاگت والے چکور راستے کو تلاش کرنے کا اصلاح کا مسئلہ-جسے عام طور پر ٹریولنگ سیلز مین کا مسئلہ کہا جاتا ہے-این پی-ہارڈ ہے۔ سب سیٹ سم کا مسئلہ ایک اور مثال ہے: انٹیجرز کے ایک سیٹ کو دیکھتے ہوئے، کیا ان میں سے کوئی غیر خالی سب سیٹ صفر تک کا اضافہ کرتا ہے؟ یہ ایک فیصلہ کا مسئلہ ہے اور این پی مکمل ہوتا ہے۔ فیصلے کے مسائل ایسے ہوتے ہیں جو این پی سخت ہوتے ہیں لیکن این پی مکمل نہیں ہوتے جیسے کہ رکنے کا مسئلہ۔ یہی وہ مسئلہ ہے جو پوچھتا ہے کہ "ایک پروگرام اور اس کے ان پٹ کو دیکھتے ہوئے، کیا یہ ہمیشہ کے لیے چلے گا؟" یہ ہاں/نہیں کا سوال ہے اور اسی طرح فیصلہ سازی کا مسئلہ بھی ہے۔ یہ ثابت کرنا آسان ہے کہ رکنے کا مسئلہ این پی سخت ہے لیکن این پی مکمل نہیں ہے۔ مثال کے طور پر، بولین کی اطمینان کے مسئلے کو ٹورنگ مشین کی تفصیل میں تبدیل کر کے رکنے کے مسئلے تک کم کیا جا سکتا ہے جو تمام سچائی کی قدر کی تفویض کی کوشش کرتا ہے اور جب اسے ایسا ملتا ہے جو فارمولے کو مطمئن کرتا ہے تو یہ رک جاتا ہے اور بصورت دیگر یہ ایک لامحدود لوپ میں چلا جاتا ہے۔ یہ دیکھنا بھی آسان ہے کہ رکنے کا مسئلہ این پی میں نہیں ہے کیونکہ این پی میں تمام مسائل محدود تعداد میں کارروائیوں میں فیصلہ کن ہیں، لیکن رکنے کا مسئلہ، عام طور پر، ناقابل فیصلہ ہے۔ این پی سخت مسائل بھی ہیں جو نہ تو این پی مکمل ہیں اور نہ ہی ناقابل فیصلہ۔ مثال کے طور پر، حقیقی مقداری بولین فارمولوں کی زبان کثیر الجہتی جگہ میں فیصلہ کن ہوتی ہے، لیکن غیر متعین کثیر الجہتی وقت میں نہیں (جب تک کہ NP = PSPACE نہ ہو)۔ این پی-نامی کنونشن این پی-ہارڈ مسائل کو پیچیدگی کلاس این پی کے عناصر ہونے کی ضرورت نہیں ہے۔ چونکہ این پی کمپیوٹیشنل پیچیدگی میں مرکزی کردار ادا کرتا ہے، اس لیے اسے کئی کلاسوں کی بنیاد کے طور پر استعمال کیا جاتا ہے: کمپیوٹیشنل فیصلے کے مسائل کی این پی کلاس جس کے لیے کسی بھی ہاں حل کی تصدیق کثیر الجہتی وقت میں ایک تعیناتی ٹورنگ مشین کے ذریعے کی جا سکتی ہے (یا کثیر الجہتی وقت میں غیر تعیناتی ٹورنگ مشین کے ذریعے حل کیا جا سکتا ہے)۔ این پی-سخت قسم کے مسائل جو کم از کم اتنے ہی سخت ہیں جتنے کہ این پی میں سب سے مشکل مسائل ہیں۔ این پی سخت مسائل این پی کے عناصر ہونے کی ضرورت نہیں ہے ؛ درحقیقت، وہ فیصلہ کن بھی نہیں ہو سکتے۔ فیصلے کے مسائل کی این پی مکمل کلاس جس میں این پی میں سب سے مشکل مسائل شامل ہیں۔ ہر این پی مکمل مسئلہ این پی میں ہونا چاہیے۔ این پی-آسان زیادہ سے زیادہ این پی کی طرح سخت، لیکن ضروری نہیں کہ این پی میں ہو۔ این پی مساوی فیصلہ کے مسائل جو این پی سخت اور این پی آسان دونوں ہیں، لیکن ضروری نہیں کہ این پی میں ہوں۔ این پی-انٹرمیڈیٹ اگر پی اور این پی مختلف ہیں، تو این پی کے علاقے میں فیصلہ سازی کے مسائل موجود ہیں جو پی اور این پی-مکمل مسائل کے درمیان آتے ہیں۔ (اگر P اور NP ایک ہی کلاس ہیں، تو NP-انٹرمیڈیٹ مسائل موجود نہیں ہیں کیونکہ اس صورت میں ہر NP-مکمل مسئلہ P میں آتا ہے، اور تعریف کے مطابق، NP میں ہر مسئلہ کو NP-مکمل مسئلہ میں کم کیا جا سکتا ہے۔) ایپلی کیشن کے شعبوں میں این پی-سخت مسائل کو اکثر ان شعبوں میں قواعد پر مبنی زبانوں کے ساتھ نمٹا جاتا ہے جن میں شامل ہیں: لگ بھگ کمپیوٹنگ کنفیگریشن کرپٹوگرافی ڈیٹا مائننگ کا فیصلہ فائیلوجنیٹکس پلاننگ کے عمل کی نگرانی اور کنٹرول روسٹرز یا شیڈول روٹنگ/وہیکل روٹنگ شیڈولنگ کی حمایت کرتا ہے مسائل کی فہرستیں بھی دیکھیں غیر حل شدہ مسائل کی فہرست میں کمی (پیچیدگی) لاعلمی حوالہ جات پیچیدگی کی کلاسیں