کیا NP پیچیدگی کی کلاس میں کوئی مسئلہ ہو سکتا ہے اگر کوئی نان ڈیٹرمنسٹک ٹیورنگ مشین ہو جو اسے کثیر وقت میں حل کر دے
سوال "کیا NP پیچیدگی کی کلاس میں کوئی مسئلہ ہو سکتا ہے اگر کوئی غیر متعین ٹورنگ مشین ہو جو اسے کثیر وقت میں حل کردے؟" کمپیوٹیشنل پیچیدگی تھیوری میں بنیادی تصورات کو چھوتا ہے۔ اس سوال کو جامع طور پر حل کرنے کے لیے، ہمیں NP پیچیدگی کے طبقے کی تعریفوں اور خصوصیات اور نان ڈیٹرمینسٹک ٹورنگ مشینوں (NDTMs) کے کردار پر غور کرنا چاہیے۔
NP کی تعریف
کلاس NP (nondeterministic polynomial time) فیصلہ کن مسائل پر مشتمل ہوتا ہے جس کے لیے ایک دیے گئے حل کی تصدیق کثیر وقت میں درست یا غلط کے طور پر ڈیٹرمنسٹک ٹورنگ مشین (DTM) کے ذریعے کی جا سکتی ہے۔ باضابطہ طور پر، NP میں فیصلہ کا مسئلہ ہے اگر کوئی کثیر وقتی تصدیقی الگورتھم موجود ہے جو مسئلہ کی مثال کے لیے دیے گئے سرٹیفکیٹ (یا گواہ) کی درستی کی تصدیق کر سکتا ہے۔
نان ڈیٹرمنسٹک ٹورنگ مشینیں
ایک نان ڈیٹرمنسٹک ٹورنگ مشین کمپیوٹیشن کا ایک نظریاتی ماڈل ہے جو ڈیٹرمنسٹک ٹورنگ مشین کی صلاحیتوں کو بڑھاتا ہے۔ ڈی ٹی ایم کے برعکس، جو اپنے منتقلی کے فنکشن کے ذریعہ بیان کردہ واحد کمپیوٹیشنل راستے کی پیروی کرتا ہے، ایک این ڈی ٹی ایم بیک وقت متعدد کمپیوٹیشنل راستوں کا تعاقب کرسکتا ہے۔ ہر قدم پر، ایک NDTM ممکنہ ٹرانزیشن کے سیٹ میں سے "منتخب" کر سکتا ہے، متوازی طور پر بہت سے ممکنہ کمپیوٹیشنز کو مؤثر طریقے سے تلاش کر سکتا ہے۔
NDTMs کے ذریعے کثیر الوقت حل پذیری
کہا جاتا ہے کہ NDTM کے ذریعہ کثیر وقت میں ایک مسئلہ حل کیا جا سکتا ہے اگر کوئی غیر متعین الگورتھم موجود ہو جو اس مسئلے کا حل کئی مراحل کے اندر تلاش کر سکتا ہے جو ان پٹ کے سائز میں کثیر الثانی ہے۔ اس کا مطلب یہ ہے کہ مسئلے کی کسی بھی مثال کے لیے، NDTM ایک ایسے کمپیوٹیشنل راستے کو تلاش کر سکتا ہے جو کثیر الثانی وقت میں حل کی طرف لے جاتا ہے۔
NP اور NDTMs کے درمیان تعلق
کلاس NP کو NDTMs کے لحاظ سے مساوی طور پر بیان کیا جا سکتا ہے۔ خاص طور پر، فیصلہ کرنے کا مسئلہ NP میں ہے اگر اور صرف اس صورت میں جب کوئی NDTM موجود ہو جو کہ کثیر وقت میں مسئلہ حل کر سکے۔ یہ مساوات اس حقیقت سے پیدا ہوتی ہے کہ ایک NDTM کسی سرٹیفکیٹ کا غیر متعین انداز میں اندازہ لگا سکتا ہے اور پھر کثیر الثانی وقت میں اس کی توثیق کر سکتا ہے۔
اس کو مثال کے ساتھ واضح کرنے کے لیے، معروف NP-complete مسئلہ، بولین اطمینان بخش مسئلہ (SAT) پر غور کریں۔ کنجیکٹیو نارمل فارم (CNF) میں بولین فارمولے کو دیکھتے ہوئے، کام یہ طے کرنا ہے کہ آیا متغیرات کے لیے سچائی اقدار کی کوئی تفویض موجود ہے جو فارمولے کو درست بناتی ہے۔ ایک NDTM غیر متعین طور پر سچائی اقدار کی تفویض کا اندازہ لگا کر اور پھر تعین کے ساتھ یہ جانچ کر کہ آیا اسائنمنٹ فارمولے کو پورا کرتی ہے، کثیر نامی وقت میں SAT کو حل کر سکتی ہے۔ توثیق کا مرحلہ، جس میں اندازہ لگایا گیا اسائنمنٹ کے تحت فارمولے کا جائزہ لینا شامل ہے، کثیر وقت میں کیا جا سکتا ہے۔
NDTMs کے ذریعہ کثیر الوقتی حل پذیری کے مضمرات
مندرجہ بالا تعریفوں اور NDTMs کے ذریعے NP اور polynomial-time solvability کے درمیان مساوات کو دیکھتے ہوئے، ہم یہ نتیجہ اخذ کر سکتے ہیں کہ اگر کوئی NDTM موجود ہے جو کثیر وقت میں کسی مسئلے کو حل کرتا ہے، تو یہ مسئلہ درحقیقت NP میں ہے۔ اس کی وجہ یہ ہے کہ اس طرح کے NDTM کی موجودگی کا مطلب یہ ہے کہ مسئلہ کے لیے ایک کثیر وقتی تصدیقی الگورتھم موجود ہے۔ NDTM کا غیر متعین اندازہ لگانے کا مرحلہ ایک سرٹیفکیٹ کی تخلیق سے مطابقت رکھتا ہے، اور تعییناتی توثیق کا مرحلہ کثیر الوقت کی تصدیق کے الگورتھم سے مساوی ہے۔
مزید غور و فکر اور مثالیں۔
اس تصور کو مزید واضح کرنے کے لیے، آئیے NP میں مسائل اور NDTMs کے ساتھ ان کے تعلقات کی اضافی مثالوں پر غور کریں:
1. ہیملٹن کے راستے کا مسئلہ: ایک گراف کو دیکھتے ہوئے، ہیملٹونین پاتھ کا مسئلہ پوچھتا ہے کہ آیا کوئی ایسا راستہ موجود ہے جو ہر ایک چوٹی کو بالکل ایک بار دیکھتا ہے۔ ایک این ڈی ٹی ایم اس مسئلے کو کثیر الثقافتی وقت میں غیر متعین طور پر عمودی کی ترتیب کا اندازہ لگا کر اور پھر اس بات کی تصدیق کر سکتا ہے کہ آیا یہ ترتیب ایک درست ہیملٹونین راستہ بناتی ہے۔ توثیقی مرحلے میں لگاتار چوٹیوں کی ملحقہ جانچ پڑتال اور اس بات کو یقینی بنانا شامل ہے کہ ہر ایک چوٹی کو بالکل ایک بار دیکھا گیا ہے، یہ دونوں ہی کثیر وقت میں کیے جا سکتے ہیں۔
2. سب سیٹ سم کا مسئلہ: عدد کے ایک سیٹ اور ہدف کی رقم کو دیکھتے ہوئے، سب سیٹ سم کا مسئلہ یہ پوچھتا ہے کہ آیا انٹیجرز کا کوئی ذیلی سیٹ موجود ہے جو ہدف تک پہنچتا ہے۔ ایک این ڈی ٹی ایم اس مسئلے کو کثیر الثقافتی وقت میں غیر متعین طور پر عدد کے ذیلی سیٹ کا اندازہ لگا کر اور پھر اس بات کی تصدیق کر سکتا ہے کہ آیا سب سیٹ کا مجموعہ ہدف کے برابر ہے۔ تصدیقی مرحلے میں تخمینہ شدہ سب سیٹ کے عناصر کا خلاصہ شامل ہوتا ہے، جو کہ کثیر وقت میں کیا جا سکتا ہے۔
3. گراف رنگنے کا مسئلہ: ایک گراف اور متعدد رنگوں کو دیکھتے ہوئے، گراف کو رنگنے کا مسئلہ یہ پوچھتا ہے کہ کیا گراف کے عمودی حصوں کو اس طرح رنگنا ممکن ہے کہ کوئی دو ملحقہ عمودی ایک ہی رنگ کا اشتراک نہ کریں۔ ایک این ڈی ٹی ایم اس مسئلے کو کثیر الثقافتی وقت میں غیر متعین طور پر رنگوں کو عمودی طور پر تفویض کرکے اور پھر اس بات کی تصدیق کر سکتا ہے کہ آیا رنگ درست ہے۔ تصدیقی مرحلے میں ملحقہ چوٹیوں کے رنگوں کی جانچ پڑتال شامل ہے، جو کہ کثیر وقت میں کیا جا سکتا ہے۔
نتیجہ
فراہم کردہ تعریفوں اور مثالوں کی روشنی میں، یہ واضح ہے کہ NP پیچیدگی کے طبقے میں کوئی مسئلہ درحقیقت ہو سکتا ہے اگر کوئی غیر متعین ٹورنگ مشین موجود ہو جو اسے کثیر الوقت میں حل کر دے گی۔ یہ تعلق کمپیوٹیشنل پیچیدگی تھیوری کا سنگ بنیاد ہے اور NDTMs کے ذریعے کثیر الوقت حل پذیری اور NP کلاس میں رکنیت کے درمیان مساوات کو واضح کرتا ہے۔
سے متعلق دیگر حالیہ سوالات اور جوابات پیچیدگی:
- کیا PSPACE کلاس EXPSPACE کلاس کے برابر نہیں ہے؟
- کیا P پیچیدگی کلاس PSPACE کلاس کا سب سیٹ ہے؟
- کیا ہم یہ ثابت کر سکتے ہیں کہ Np اور P کلاس یکساں ہیں کسی بھی NP مکمل مسئلے کے لیے ایک مؤثر کثیر الثانی حل تلاش کر کے ایک deterministic TM پر؟
- کیا NP کلاس EXPTIME کلاس کے برابر ہو سکتی ہے؟
- کیا PSPACE میں ایسے مسائل ہیں جن کے لیے کوئی معلوم NP الگورتھم نہیں ہے؟
- کیا SAT کا مسئلہ NP مکمل مسئلہ ہوسکتا ہے؟
- NP زبانوں کی کلاس ہے جس میں متعدد وقت کی تصدیق ہوتی ہے۔
- کیا P اور NP دراصل ایک ہی پیچیدگی کی کلاس ہے؟
- کیا P پیچیدگی کی کلاس میں ہر سیاق و سباق سے پاک زبان ہے؟
- کیا پولنومیل ٹائم ویریفائرز کے ساتھ فیصلہ کن مسائل کی ایک کلاس کے طور پر NP کی تعریف اور اس حقیقت کے درمیان کوئی تضاد ہے کہ کلاس P میں مسائل میں بھی polynomial-time verifiers ہوتے ہیں؟
Complexity میں مزید سوالات اور جوابات دیکھیں