RE (complexity)
કોમ્પ્યુટેબિલિટી થિયરી અને કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરીમાં, આરઇ (પુનરાવર્તિત રીતે ગણનાપાત્ર) એ નિર્ણય સમસ્યાઓનો વર્ગ છે, જેના માટે 'હા' જવાબને ટ્યુરિંગ મશીન દ્વારા મર્યાદિત સમયમાં ચકાસી શકાય છે. અનૌપચારિક રીતે, તેનો અર્થ એ છે કે જો સમસ્યાના ઉદાહરણનો જવાબ 'હા' હોય, તો કેટલીક પ્રક્રિયા છે જે આ નક્કી કરવા માટે મર્યાદિત સમય લે છે, અને જ્યારે સાચો જવાબ 'ના' હોય ત્યારે આ પ્રક્રિયા ક્યારેય ખોટી રીતે 'હા' નો અહેવાલ આપતી નથી. જો કે, જ્યારે સાચો જવાબ 'ના' હોય, ત્યારે પ્રક્રિયા અટકાવવાની જરૂર નથી; તે કેટલાક 'ના' કિસ્સાઓ માટે 'અનંત લૂપ' માં જઈ શકે છે. આવી પ્રક્રિયાને કેટલીકવાર અર્ધ-અલ્ગોરિધમ કહેવામાં આવે છે, જે તેને અલ્ગોરિધમથી અલગ પાડે છે, જેને નિર્ણયની સમસ્યાના સંપૂર્ણ ઉકેલ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. તેવી જ રીતે, કો-આરઇ એ તમામ ભાષાઓનો સમૂહ છે જે આરઇમાં ભાષાના પૂરક છે. એક અર્થમાં, કો-આરઈમાં એવી ભાષાઓ છે કે જેના સભ્યપદને મર્યાદિત સમયગાળામાં નકારી શકાય છે, પરંતુ સભ્યપદ સાબિત કરવામાં કાયમ સમય લાગી શકે છે. સમકક્ષ વ્યાખ્યા સમાનરૂપે, આરઇ એ નિર્ણય સમસ્યાઓનો વર્ગ છે જેના માટે ટ્યુરિંગ મશીન એક પછી એક તમામ 'હા' ઉદાહરણોની યાદી બનાવી શકે છે (આ તે છે જે 'ગણનાપાત્ર' અર્થ છે). આરઈનો દરેક સભ્ય પુનરાવર્તિત રીતે ગણી શકાય તેવો સમૂહ છે અને તેથી તે એક ડાયોફેન્ટાઇન સમૂહ છે. આ સમકક્ષ છે તે બતાવવા માટે, નોંધ લો કે જો કોઈ મશીન હોય જે તમામ સ્વીકૃત ઇનપુટ્સની ગણતરી કરે છે, તો અન્ય મશીન કે જે સ્ટ્રિંગમાં લે છે તે ચલાવી શકે છે અને જો સ્ટ્રિંગની ગણતરી કરવામાં આવે તો સ્વીકારી શકે છે. તેનાથી વિપરીત, જો કોઈ મશીન કોઈ ભાષામાં ઇનપુટ હોય ત્યારે સ્વીકારે છે, તો અન્ય મશીન દરેક ઇનપુટ પરના સિમ્યુલેશનને એકબીજા સાથે જોડીને અને સ્વીકારવામાં આવેલા સ્ટ્રિંગ્સને આઉટપુટ કરીને ભાષામાં તમામ સ્ટ્રિંગ્સની ગણતરી કરી શકે છે (એક્ઝેક્યુશનનો એક ક્રમ છે જે આખરે દરેક એક્ઝેક્યુશન સ્ટેપ સુધી પહોંચશે કારણ કે તેમાં ઇનપુટ્સ અને સ્ટેપની સંખ્યાબંધ જોડી હોય છે). અન્ય વર્ગો સાથેના સંબંધો પુનરાવર્તિત ભાષાઓ (આર) નો સમૂહ એ આરઈ અને કો-આરઈ બંનેનો સબસેટ છે. હકીકતમાં, તે તે બે વર્ગોનું આંતરછેદ છે, કારણ કે આપણે કોઈ પણ સમસ્યાને નક્કી કરી શકીએ છીએ કે જેના માટે ઓળખકર્તા અને સહ-ઓળખકર્તા પણ અસ્તિત્વમાં છે, જ્યાં સુધી કોઈ પરિણામ ન મળે ત્યાં સુધી તેમને ફક્ત એકબીજા સાથે જોડીને. તેથીઃ તેનાથી વિપરીત, એવી ભાષાઓનો સમૂહ કે જે ન તો RE છે અને ન તો સહ-RE છે, તેને NRNC તરીકે ઓળખવામાં આવે છે. આ એવી ભાષાઓનો સમૂહ છે જેના માટે ન તો સભ્યપદ કે ન તો બિન-સભ્યપદ મર્યાદિત સમયગાળામાં સાબિત થઈ શકે છે, અને તેમાં અન્ય તમામ ભાષાઓ છે જે આરઈ અથવા કો-આરઈમાં નથી. તે છેઃ આ સમસ્યાઓ માત્ર અનિર્ણાયક જ નથી, પરંતુ ન તો તેઓ અને ન તો તેમના પૂરક પુનરાવર્તિત રીતે ગણવા યોગ્ય છે. જાન્યુઆરી 2020 માં, એક પ્રીપ્રિન્ટે એક સાબિતીની જાહેરાત કરી હતી કે આરઇ વર્ગ એમઆઇપી * ની સમકક્ષ છે (તે વર્ગ જ્યાં શાસ્ત્રીય ચકાસણી કરનાર બહુવિધ સર્વ-શક્તિશાળી ક્વોન્ટમ પ્રોવર્સ સાથે ક્રિયાપ્રતિક્રિયા કરે છે જે ગૂંચવણ શેર કરે છે); એક સુધારેલ, પરંતુ હજી સુધી સંપૂર્ણ સમીક્ષા કરાયેલ નથી, સાબિતી નવેમ્બર 2021 માં કોમ્યુનિકેશન્સ ઓફ ધ એસીએમમાં પ્રકાશિત કરવામાં આવી હતી. પુરાવો સૂચવે છે કે કોનેસ એમ્બેડિંગ સમસ્યા અને સિરેલસનની સમસ્યા ખોટી છે. રી-કમ્પ્લીટ રી-કમ્પ્લીટ એ નિર્ણયની સમસ્યાઓનો સમૂહ છે જે આરઈ માટે પૂર્ણ છે. એક અર્થમાં, આ "સૌથી મુશ્કેલ" પુનરાવર્તિત રીતે ગણી શકાય તેવી સમસ્યાઓ છે. સામાન્ય રીતે, ઉપયોગમાં લેવાતા ઘટાડા પર કોઈ પ્રતિબંધ મૂકવામાં આવતો નથી સિવાય કે તે ઘણા-એક ઘટાડા હોવા જોઈએ. ફરીથી પૂર્ણ સમસ્યાઓના ઉદાહરણોઃ સમસ્યાને અટકાવવીઃ શું મર્યાદિત ઇનપુટ આપવામાં આવેલ પ્રોગ્રામ ચાલુ રહે છે કે કાયમ ચાલશે. રાઇસના પ્રમેય અનુસાર, પુનરાવર્તિત કાર્યોના સમૂહના કોઈપણ બિન-તુચ્છ સબસેટમાં સભ્યપદ નક્કી કરવું એ આરઈ-હાર્ડ છે. જ્યારે પણ સેટ પુનરાવર્તિત રીતે ગણવા યોગ્ય હશે ત્યારે તે પૂર્ણ થશે. સાબિત કર્યું કે તમામ સર્જનાત્મક સમૂહો ફરીથી પૂર્ણ છે. જૂથો અથવા અર્ધ જૂથો માટે એકસમાન શબ્દ સમસ્યા. (ખરેખર, કેટલાક વ્યક્તિગત જૂથો માટે સમસ્યા શબ્દ ફરીથી પૂર્ણ છે.) સામાન્ય અનિયંત્રિત ઔપચારિક વ્યાકરણમાં સભ્યપદ નક્કી કરવું. (ફરીથી, અમુક વ્યક્તિગત વ્યાકરણમાં ફરીથી પૂર્ણ સભ્યપદની સમસ્યાઓ હોય છે.) પ્રથમ ક્રમના તર્ક માટે માન્યતા સમસ્યા. પત્રવ્યવહાર પછીની સમસ્યાઃ તારની જોડીની સૂચિ જોતાં, નક્કી કરો કે આ જોડીમાંથી કોઈ પસંદગી છે કે કેમ (પુનરાવર્તનને મંજૂરી આપવી) જેથી પ્રથમ વસ્તુઓનું (જોડીનું) સંયોજન બીજી વસ્તુઓના સંયોજન બરાબર હોય. ડાયોફેન્ટાઇન સમીકરણમાં કોઈ પૂર્ણાંક ઉકેલો છે કે કેમ તે નક્કી કરવું. સહ-આરઇ-પૂર્ણ સહ-આરઇ-પૂર્ણ એ નિર્ણય સમસ્યાઓનો સમૂહ છે જે સહ-આરઇ માટે પૂર્ણ છે. એક અર્થમાં, આ સૌથી મુશ્કેલ પુનરાવર્તિત રીતે ગણી શકાય તેવી સમસ્યાઓનું પૂરક છે. સહ-આરઇ-પૂર્ણ સમસ્યાઓના ઉદાહરણોઃ વાંગ ટાઇલ્સ માટે ડોમીનો સમસ્યા. પ્રથમ ક્રમના તર્ક માટે સંતોષકારક સમસ્યા. ક્નુથ-બેન્ડિક્સ કમ્પ્લીશન અલ્ગોરિધમ પણ જુઓ અનિર્ણિત સમસ્યાઓની સૂચિ પોલીમોર્ફિક રિકર્શન રીશ અલ્ગોરિધમ સેમીડેસિડેબિલિટી સંદર્ભો જટિલતા વર્ગો અનિર્ણિત સમસ્યાઓ