EXPSPACE
કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરીમાં, ઘાતાંકીય અવકાશમાં, એટલે કે અવકાશમાં, એક નિર્ધારક ટ્યુરિંગ મશીન દ્વારા ઉકેલી શકાય તેવી તમામ નિર્ણય સમસ્યાઓનો સમૂહ છે, જ્યાં તેનું બહુપદી કાર્ય છે. કેટલાક લેખકો રેખીય કાર્યને પ્રતિબંધિત કરે છે, પરંતુ મોટાભાગના લેખકો તેના બદલે પરિણામી વર્ગને બોલાવે છે. જો આપણે તેના બદલે બિનનિર્ધારણીય મશીનનો ઉપયોગ કરીએ, તો આપણને વર્ગ મળે છે, જે સેવિચના પ્રમેયની બરાબર છે. નિર્ણયની સમસ્યા એ છે કે જો તે અંદર હોય, અને અંદરની દરેક સમસ્યામાં બહુપદી-સમય અનેક-એક ઘટાડો હોય છે. બીજા શબ્દોમાં કહીએ તો, એક બહુપદી-સમય અલ્ગોરિધમ છે જે એક જ જવાબ સાથે એકના ઉદાહરણોને બીજાના ઉદાહરણોમાં પરિવર્તિત કરે છે. સમસ્યાઓને સૌથી મુશ્કેલ સમસ્યા તરીકે ગણી શકાય. તે, અને નું કડક સુપરસેટ છે અને તેનું કડક સુપરસેટ હોવાનું માનવામાં આવે છે. ઔપચારિક વ્યાખ્યા અને, સમસ્યાઓના ઉદાહરણોના સંદર્ભમાં સમસ્યાનું ઉદાહરણ એ ઓળખવાની સમસ્યા છે કે બે નિયમિત અભિવ્યક્તિઓ જુદી જુદી ભાષાઓનું પ્રતિનિધિત્વ કરે છે કે કેમ, જ્યાં અભિવ્યક્તિઓ ચાર સંચાલકો સુધી મર્યાદિત છેઃ જોડાણ, સંયોજન, ક્લેન સ્ટાર (અભિવ્યક્તિની શૂન્ય અથવા વધુ નકલો), અને વર્ગ (અભિવ્યક્તિની બે નકલો). જો ક્લાઈન સ્ટારને છોડી દેવામાં આવે, તો તે સમસ્યા બની જાય છે, જે આના જેવી છે, સિવાય કે તેને નિર્ધારિત કરવાને બદલે બિન-નિર્ધારિત ટ્યુરિંગ મશીનોની દ્રષ્ટિએ વ્યાખ્યાયિત કરવામાં આવે છે. એલ. બર્મન દ્વારા 1980 માં એવું પણ દર્શાવવામાં આવ્યું છે કે વાસ્તવિક સંખ્યાઓ વિશેના કોઈપણ પ્રથમ ક્રમના નિવેદનની ચકાસણી/ખોટી રજૂઆતની સમસ્યા જેમાં માત્ર ઉમેરો અને સરખામણી (પરંતુ કોઈ ગુણાકાર નથી) નો સમાવેશ થાય છે. અલુર અને હેન્ઝિન્ગરે સમય (પૂર્ણાંક) સાથે રેખીય અસ્થાયી તર્કને વિસ્તૃત કર્યો અને સાબિત કર્યું કે તેમના તર્કની માન્યતા સમસ્યા EXPSPACE-પૂર્ણ છે. પેટ્રી નેટ્સ માટે કવરેજની સમસ્યા-પૂર્ણ છે. પેટ્રી જાળી માટે પહોંચવાની સમસ્યા લાંબા સમયથી-સખત હોવાનું જાણીતું હતું, પરંતુ તે બિનઅનુભવી હોવાનું દર્શાવવામાં આવ્યું હતું, તેથી તે કદાચ અંદર નથી. અન્ય વર્ગો સાથેના સંબંધો, અને ના કડક ઉપગણ તરીકે ઓળખાય છે. તે એક કડક સુપરસેટ હોવાની વધુ શંકા છે, જો કે આ જાણીતું નથી. રમત જટિલતા સંદર્ભો વિભાગ 9.1.1: ઘાતાંકીય અવકાશ પૂર્ણતા, પૃષ્ઠો. 313-317 પણ જુઓ. દર્શાવે છે કે ઘાતાંક સાથે નિયમિત અભિવ્યક્તિઓની સમાનતા નક્કી કરવી એ EXPSPACE-પૂર્ણ છે. જટિલતા વર્ગો