R (complexity)
کمپیوٹیشنل پیچیدگی کے نظریہ میں، آر ٹورنگ مشین کے ذریعے حل کیے جانے والے فیصلہ سازی کے مسائل کی کلاس ہے، جو تمام تکراری زبانوں کا مجموعہ ہے (جسے فیصلہ کن زبانیں بھی کہا جاتا ہے)۔ مساوی فارمولیشن R اس معنی میں تمام کل کمپیوٹیبل فنکشنز کے سیٹ کے برابر ہے کہ: ایک فیصلہ مسئلہ R میں ہے اگر اور صرف اس صورت میں جب اس کا انڈیکیٹر فنکشن کمپیوٹیبل ہو، کل فنکشن تب اور صرف اس صورت میں کمپیوٹیبل ہوتا ہے جب اس کا گراف R میں ہو۔ دیگر کلاسوں کے ساتھ تعلق چونکہ ہم کسی بھی مسئلے کا فیصلہ کر سکتے ہیں جس کے لیے ایک شناخت کنندہ اور شریک شناخت کنندہ موجود ہو صرف ان کو آپس میں جوڑ کر جب تک کہ کوئی نتیجہ حاصل نہ کر لے، کلاس RE کے برابر ہے۔ حوالہ جات بلم، لینور، مائیک شوب، اور اسٹیو سمیل، (1989)، "حقیقی اعداد پر کمپیوٹیشن اور پیچیدگی کے نظریہ پر: این پی-تکمیل، تکراری افعال اور عالمگیر مشینیں"، بلیٹن آف دی امریکن میتھمیٹیکل سوسائٹی، نیو سیریز، 21 (1): 1-46۔ بیرونی روابط پیچیدگی کلاسیں