Promise problem
کمپیوٹیشنل پیچیدگی کے نظریہ میں، وعدے کا مسئلہ کسی فیصلے کے مسئلے کی عمومی شکل ہے جہاں ان پٹ کا وعدہ کیا جاتا ہے کہ وہ تمام ممکنہ ان پٹ کے کسی خاص ذیلی سیٹ سے تعلق رکھتا ہے۔ فیصلے کے مسائل کے برعکس، ہاں کی مثالیں (وہ ان پٹ جن کے لیے ایک الگورتھم کو ہاں واپس کرنا چاہیے) اور کوئی بھی مثال تمام ان پٹ کے سیٹ کو ختم نہیں کرتی ہے۔ بدیہی طور پر، الگورتھم سے وعدہ کیا گیا ہے کہ ان پٹ درحقیقت ہاں یا نہیں مثالوں کے سیٹ سے تعلق رکھتا ہے۔ ایسے ان پٹ ہو سکتے ہیں جو نہ تو ہاں میں ہیں اور نہ ہی۔ اگر اس طرح کا ان پٹ کسی وعدے کے مسئلے کو حل کرنے کے لیے کسی الگورتھم کو دیا جاتا ہے، تو الگورتھم کو کسی بھی چیز کو آؤٹ پٹ کرنے کی اجازت ہوتی ہے، اور وہ رک بھی نہیں سکتا۔ رسمی تعریف ایک فیصلہ کا مسئلہ کسی زبان سے وابستہ ہو سکتا ہے، جہاں مسئلہ یہ ہے کہ تمام ان پٹ کو قبول کیا جائے اور ان تمام ان پٹ کو مسترد کیا جائے جو اس میں نہیں ہیں۔ وعدے کے مسئلے کے لیے، دو زبانیں ہیں، اور، جو الگ الگ ہونی چاہئیں، جس کا مطلب ہے، کہ تمام ان پٹ کو قبول کرنا ہے اور تمام ان پٹ کو مسترد کرنا ہے۔ سیٹ کو وعدہ کہا جاتا ہے۔ اگر ان پٹ کا تعلق وعدے سے نہیں ہے تو آؤٹ پٹ پر کوئی تقاضے نہیں ہیں۔ اگر وعدہ برابر ہے، تو یہ بھی ایک فیصلہ سازی کا مسئلہ ہے، اور وعدہ کو معمولی کہا جاتا ہے۔ مثالیں بہت سے قدرتی مسائل دراصل وعدے کے مسائل ہوتے ہیں۔ مثال کے طور پر، مندرجہ ذیل مسئلے پر غور کریں: ایک ہدایت شدہ سایکلک گراف کو دیکھتے ہوئے، اس بات کا تعین کریں کہ آیا گراف کی لمبائی 10 ہے۔ ہاں مثالوں کو 10 کی لمبائی کے راستے کے ساتھ سایکلک گرافوں کی ہدایت کی جاتی ہے، جبکہ کوئی مثالوں کو سایکلک گرافوں کی ہدایت نہیں کی جاتی ہے جس کی لمبائی 10 نہیں ہوتی ہے۔ وعدہ ڈائریکٹڈ ایسائکلک گراف کا مجموعہ ہے۔ اس مثال میں، وعدے کی جانچ کرنا آسان ہے۔ خاص طور پر، یہ چیک کرنا بہت آسان ہے کہ آیا دیا گیا گراف چکور ہے یا نہیں۔ تاہم، وعدہ شدہ جائیداد کا اندازہ لگانا مشکل ہو سکتا ہے۔ مثال کے طور پر، اس مسئلے پر غور کریں "ہیملٹنین گراف کو دیکھتے ہوئے، اس بات کا تعین کریں کہ آیا گراف کا سائیکل سائز 4 کا ہے"۔ اب وعدے کا اندازہ لگانا این پی مشکل ہے، پھر بھی وعدے کے مسئلے کو حل کرنا آسان ہے کیونکہ سائز 4 کے چکروں کی جانچ کثیر الجہتی وقت میں کی جا سکتی ہے۔ کمپیوٹیشنل مسئلہ فیصلہ مسئلہ آپٹیمائزیشن مسئلہ تلاش مسئلہ گنتی مسئلہ (پیچیدگی) فنکشن مسئلہ TFNP حوالہ جات سروے کمپیوٹیشنل مسائل