PR (complexity)
પીઆર એ તમામ આદિમ પુનરાવર્તિત કાર્યોનો જટિલતા વર્ગ છે-અથવા, સમાનરૂપે, તમામ ઔપચારિક ભાષાઓનો સમૂહ કે જે આવા કાર્ય દ્વારા બંધાયેલા સમયમાં નક્કી કરી શકાય છે. આમાં ઉમેરો, ગુણાકાર, ઘાતાંક, સંકોચન વગેરેનો સમાવેશ થાય છે. એકરમેન કાર્ય એ એવા કાર્યનું ઉદાહરણ છે જે આદિમ પુનરાવર્તિત નથી, જે દર્શાવે છે કે PR સખત રીતે R (કૂપર 2004:88) માં સમાયેલ છે. બીજી બાજુ, આપણે નીચેના અર્થમાં પ્રિમિટિવ-રિકર્સિવ ફંક્શન દ્વારા કોઈપણ રિકર્સિવલી એન્યુમરેબલ સેટ (તેની કોમ્પ્લેક્સિટી ક્લાસ RE પણ જુઓ) ને "ગણના" કરી શકીએ છીએઃ ઇનપુટ (M, k) આપવામાં આવે છે, જ્યાં M એ ટ્યુરિંગ મશીન છે અને k એ પૂર્ણાંક છે, જો M એ k સ્ટેપની અંદર અટકે છે તો M આઉટપુટ કરે છે; અન્યથા કંઇ આઉટપુટ થતું નથી. પછી તમામ સંભવિત ઇનપુટ્સ (M, k) પર આઉટપુટનું જોડાણ બરાબર M નો સમૂહ છે જે અટકી જાય છે. પીઆરમાં સખત રીતે એલિમેન્ટરીનો સમાવેશ થાય છે. પીઆરમાં "પીઆર-પૂર્ણ" સમસ્યાઓ હોતી નથી (ધારો કે, દા. ત., ELEMENTARY સાથે સંબંધિત ઘટાડો). વ્યવહારમાં, ઘણી સમસ્યાઓ કે જે પીઆરમાં નથી પરંતુ માત્ર તેનાથી આગળ છે-પૂર્ણ છે (શ્મિટ્ઝ 2016). સંદર્ભો બાહ્ય કડીઓ. જટિલતા વર્ગો