RE (complexity)
کمپیوٹیبلٹی تھیوری اور کمپیوٹیشنل پیچیدگی تھیوری میں، آر ای (بار بار قابل شمار) فیصلہ سازی کے مسائل کی وہ کلاس ہے جس کے لیے 'ہاں' کے جواب کی تصدیق ٹورنگ مشین کے ذریعے ایک محدود وقت میں کی جا سکتی ہے۔ غیر رسمی طور پر، اس کا مطلب یہ ہے کہ اگر کسی مسئلے کی مثال کا جواب 'ہاں' ہے، تو کچھ طریقہ کار ہے جو اس کا تعین کرنے میں محدود وقت لگتا ہے، اور یہ طریقہ کار کبھی بھی غلط طور پر 'ہاں' کی اطلاع نہیں دیتا ہے جب صحیح جواب 'نہیں' ہوتا ہے۔ تاہم، جب صحیح جواب 'نہیں' ہوتا ہے، تو طریقہ کار کو روکنے کی ضرورت نہیں ہوتی ہے ؛ یہ کچھ 'نہیں' معاملات کے لیے "لامحدود لوپ" میں جا سکتا ہے۔ اس طرح کے طریقہ کار کو بعض اوقات سیمی الگورتھم کہا جاتا ہے، تاکہ اسے الگورتھم سے الگ کیا جا سکے، جس کی تعریف کسی فیصلہ سازی کے مسئلے کے مکمل حل کے طور پر کی جاتی ہے۔ اسی طرح، کو-آر ای ان تمام زبانوں کا مجموعہ ہے جو آر ای میں کسی زبان کی تکمیل ہیں۔ ایک لحاظ سے، کو-آر ای میں ایسی زبانیں شامل ہیں جن کی رکنیت کو محدود وقت میں غلط ثابت کیا جا سکتا ہے، لیکن رکنیت ثابت کرنے میں ہمیشہ کا وقت لگ سکتا ہے۔ مساوی تعریف مساوی طور پر، آر ای فیصلہ سازی کے مسائل کی وہ کلاس ہے جس کے لیے ٹورنگ مشین ایک ایک کر کے تمام 'ہاں' مثالوں کی فہرست بنا سکتی ہے (یہی 'قابل شمار' کا مطلب ہے)۔ آر ای کا ہر رکن ایک بار بار شمار ہونے والا سیٹ ہے اور اس لیے ایک ڈیوفنٹائن سیٹ ہے۔ یہ ظاہر کرنے کے لیے کہ یہ مساوی ہے، نوٹ کریں کہ اگر کوئی ایسی مشین ہے جو تمام قبول شدہ ان پٹ کو شمار کرتی ہے، تو ایک دوسری مشین جو سٹرنگ میں لے جاتی ہے چل سکتی ہے اور قبول کر سکتی ہے اگر سٹرنگ کو شمار کیا گیا ہے۔ اس کے برعکس، اگر کوئی مشین قبول کرتی ہے جب کوئی ان پٹ کسی زبان میں ہوتا ہے، تو دوسری مشین ہر ان پٹ کے تخروپن کو آپس میں جوڑ کر اور قبول شدہ تاروں کو آؤٹ پٹ کر کے زبان میں تمام تاروں کی گنتی کر سکتی ہے (عمل درآمد کا ایک آرڈر ہوتا ہے جو بالآخر ہر عمل درآمد کے مرحلے تک پہنچ جاتا ہے کیونکہ ان پٹ اور مراحل کے بہت سے ترتیب شدہ جوڑے ہوتے ہیں)۔ دیگر طبقات سے تعلقات تکراری زبانوں (R) کا مجموعہ RE اور Co-RE دونوں کا ایک ذیلی مجموعہ ہے۔ درحقیقت، یہ ان دونوں کلاسوں کا چوراہا ہے، کیونکہ ہم کسی بھی مسئلے کا فیصلہ اس وقت تک کر سکتے ہیں جب تک کہ کوئی نتیجہ حاصل نہ کر لے۔ اس لیے: اس کے برعکس، ایسی زبانوں کا مجموعہ جو نہ تو آر ای ہے اور نہ ہی کو-آر ای ہے، این آر این سی کے نام سے جانا جاتا ہے۔ یہ ان زبانوں کا مجموعہ ہے جن کے لیے نہ تو رکنیت اور نہ ہی غیر رکنیت کو محدود وقت میں ثابت کیا جا سکتا ہے، اور دیگر تمام زبانوں پر مشتمل ہے جو RE یا Co-RE میں نہیں ہیں۔ یہ ہے: نہ صرف یہ مسائل ناقابل فیصلہ ہیں، بلکہ نہ تو وہ اور نہ ہی ان کی تکمیل بار بار قابل ذکر ہیں۔ جنوری 2020 میں، ایک پری پرنٹ نے اس ثبوت کا اعلان کیا کہ آر ای کلاس ایم آئی پی * کے مساوی تھا (وہ کلاس جہاں ایک کلاسیکی تصدیق کنندہ متعدد طاقتور کوانٹم پروورز کے ساتھ تعامل کرتا ہے جو الجھن کا اشتراک کرتے ہیں) ؛ ایک نظر ثانی شدہ، لیکن ابھی تک مکمل طور پر جائزہ نہیں لیا گیا، ثبوت نومبر 2021 میں کمیونیکیشنز آف اے سی ایم میں شائع کیا گیا تھا۔ ثبوت سے پتہ چلتا ہے کہ کونس ایمبیڈنگ کا مسئلہ اور سیرلسن کا مسئلہ غلط ہے۔ دوبارہ مکمل RE-مکمل فیصلہ سازی کے مسائل کا مجموعہ ہے جو RE کے لیے مکمل ہوتے ہیں۔ ایک لحاظ سے، یہ "سب سے مشکل" بار بار شمار ہونے والے مسائل ہیں۔ عام طور پر، استعمال کی جانے والی کٹوتیوں پر کوئی پابندی نہیں لگائی جاتی ہے سوائے اس کے کہ ان میں کئی ایک کٹوتیاں ہونی چاہئیں۔ دوبارہ مکمل ہونے والے مسائل کی مثالیں: مسئلہ کو روکنا: آیا ایک محدود ان پٹ دیا گیا پروگرام چل رہا ہے یا ہمیشہ کے لیے چلے گا۔ رائس کے نظریہ کے مطابق، تکراری افعال کے سیٹ کے کسی بھی غیر معمولی ذیلی سیٹ میں رکنیت کا فیصلہ کرنا RE-مشکل ہے۔ جب بھی سیٹ بار بار شمار کیا جائے گا تو یہ مکمل ہو جائے گا۔ ثابت کیا کہ تمام تخلیقی سیٹ دوبارہ مکمل ہیں۔ گروپوں یا نیم گروپوں کے لیے یکساں لفظ کا مسئلہ۔ (درحقیقت، کچھ انفرادی گروپوں کے لیے لفظ مسئلہ دوبارہ مکمل ہے۔) عام غیر محدود رسمی گرائمر میں رکنیت کا فیصلہ کرنا۔ (پھر، بعض انفرادی گرائمرز میں دوبارہ مکمل رکنیت کے مسائل ہوتے ہیں۔) فرسٹ آرڈر منطق کے لیے توثیق کا مسئلہ۔ خط و کتابت کے بعد کا مسئلہ: تاروں کے جوڑوں کی فہرست کو دیکھتے ہوئے، اس بات کا تعین کریں کہ آیا ان جوڑوں میں سے کوئی انتخاب ہے (دہرانے کی اجازت دیتا ہے) تاکہ پہلی اشیاء (جوڑوں کی) کا امتزاج دوسری اشیاء کے امتزاج کے برابر ہو۔ اس بات کا تعین کرنا کہ آیا ڈیوفنٹائن مساوات کا کوئی انٹیجر حل ہے۔ کو-آر ای-مکمل فیصلہ سازی کے مسائل کا مجموعہ ہے جو کو-آر ای کے لیے مکمل ہوتے ہیں۔ ایک لحاظ سے، یہ سب سے مشکل بار بار شمار ہونے والے مسائل کی تکمیل ہیں۔ شریک-آر ای-مکمل مسائل کی مثالیں: وانگ ٹائلوں کے لیے ڈومینو مسئلہ۔ فرسٹ آرڈر منطق کے لیے اطمینان کا مسئلہ۔ یہ بھی دیکھیں Knuth-Bendix تکمیل الگورتھم ناقابل فیصلہ مسائل کی فہرست پولیمورفک ریکرشن رسک الگورتھم سیمیڈیسیڈیبلٹی حوالہ جات پیچیدگی کلاسیں ناقابل فیصلہ مسائل