R (complexity)
કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરીમાં, આર એ ટ્યુરિંગ મશીન દ્વારા ઉકેલી શકાય તેવી નિર્ણય સમસ્યાઓનો વર્ગ છે, જે તમામ પુનરાવર્તિત ભાષાઓનો સમૂહ છે (જેને નિર્ણાયક ભાષાઓ પણ કહેવાય છે). સમકક્ષ ફોર્મ્યુલેશન આર એ અર્થમાં તમામ કુલ ગણતરીપાત્ર કાર્યોના સમૂહની સમકક્ષ છે કેઃ નિર્ણયની સમસ્યા આરમાં હોય છે જો અને માત્ર ત્યારે જ જો તેનું સૂચક કાર્ય ગણતરીપાત્ર હોય, તો કુલ કાર્ય ગણતરીપાત્ર હોય છે જો અને માત્ર ત્યારે જ જો તેનો આલેખ આરમાં હોય. અન્ય વર્ગો સાથેનો સંબંધ કારણ કે આપણે કોઈ પણ સમસ્યા નક્કી કરી શકીએ છીએ કે જેના માટે ઓળખકર્તા અને સહ-ઓળખકર્તા પણ અસ્તિત્વમાં છે, જ્યાં સુધી કોઈ પરિણામ ન મળે ત્યાં સુધી તેમને ફક્ત એકબીજા સાથે જોડીને, વર્ગ આરઇ કો-આરઇ બરાબર છે. સંદર્ભો બ્લમ, લેનોર, માઇક શુબ અને સ્ટીવ સ્મેલ, (1989), "વાસ્તવિક સંખ્યાઓ પર ગણતરી અને જટિલતાના સિદ્ધાંત પરઃ એન. પી.-પૂર્ણતા, પુનરાવર્તિત કાર્યો અને સાર્વત્રિક મશીનો", બુલેટિન ઓફ ધ અમેરિકન મેથેમેટિકલ સોસાયટી, નવી શ્રેણી, 21 (1): 1-46. બાહ્ય કડીઓ જટિલતા વર્ગો