EXPTIME
કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરીમાં, જટિલતા વર્ગ EXPTIME (કેટલીકવાર EXP અથવા DEXPTIME તરીકે ઓળખાય છે) એ તમામ નિર્ણય સમસ્યાઓનો સમૂહ છે જે ઘાતાંકીય સમયમાં નિર્ધારક ટ્યુરિંગ મશીન દ્વારા ઉકેલી શકાય છે, એટલે કે, O (2p (n) સમયમાં, જ્યાં p (n) એ n નું બહુપદી કાર્ય છે. ઉદાહરણ તરીકે, વર્ગ 2-EXPTIME ને EXPTIME ની જેમ જ વ્યાખ્યાયિત કરવામાં આવે છે પરંતુ બમણી ઘાતાંકીય સમય મર્યાદા સાથે. આને ઉચ્ચ અને ઉચ્ચ સમય મર્યાદા સુધી સામાન્યીકૃત કરી શકાય છે. EXPTIME ને અવકાશ વર્ગ APSPACE તરીકે પણ પુનઃરચના કરી શકાય છે, જે બહુપદી અવકાશમાં વૈકલ્પિક ટ્યુરિંગ મશીન દ્વારા ઉકેલી શકાય તેવી તમામ સમસ્યાઓનો સમૂહ છે. EXPTIME અન્ય મૂળભૂત સમય અને અવકાશ જટિલતા વર્ગો સાથે નીચેની રીતે સંબંધિત છેઃ P. N. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P વધુમાં, સમય પદાનુક્રમ પ્રમેય અને અવકાશ પદાનુક્રમ પ્રમેય દ્વારા, તે જાણીતું છે કે પી. એક્સ. પી. ટી. આઈ. એમ. ઈ., એન. પી. એક્સ. પી. ટી. આઈ. એમ. ઈ. અને પી. એસ. પી. એ. સી. ઈ. એક્સ. પી. એસ. પી. ઈ. ઔપચારિક વ્યાખ્યા ડી. ટી. આઈ. એમ. ઈ. ની દ્રષ્ટિએ, અન્ય વર્ગો સાથેના સંબંધો તે પણ જાણીતું છે કે, સમય પદાનુક્રમ પ્રમેય અને અવકાશ પદાનુક્રમ પ્રમેય દ્વારા, ઉપરોક્ત અભિવ્યક્તિઓમાં, પ્રતીકનો અર્થ "નો સબસેટ છે", અને પ્રતીકનો અર્થ "નો કડક સબસેટ છે". તેથી પ્રથમ ત્રણ સમાવેશમાંથી ઓછામાં ઓછો એક અને છેલ્લા ત્રણ સમાવેશમાંથી ઓછામાં ઓછો એક યોગ્ય હોવો જોઈએ, પરંતુ તે જાણીતું નથી કે કયા છે. મોટાભાગના નિષ્ણાતો માને છે કે તમામ સમાવેશ યોગ્ય છે. તે પણ જાણીતું છે કે જો P = NP હોય, તો EXPTIME NEXPTIME, બિનનિર્ધારિત ટ્યુરિંગ મશીન દ્વારા ઘાતાંકીય સમયમાં ઉકેલી શકાય તેવી સમસ્યાઓનો વર્ગ છે. વધુ સ્પષ્ટ રીતે કહીએ તો, જો અને માત્ર ત્યારે જ જો એન. પી. માં વિરલ ભાષાઓ અસ્તિત્વમાં હોય જે પી. એક્સ. પી. ટી. આઈ. એમ. ઈ. માં ન હોય તો તેને અવકાશ વર્ગ એ. પી. એસ. પી. એ. સી. ઇ. તરીકે પુનઃરચના કરી શકાય છે, જે બહુપદી અવકાશમાં વૈકલ્પિક ટ્યુરિંગ મશીન દ્વારા ઉકેલી શકાય તેવી તમામ સમસ્યાઓનો સમૂહ છે. તે જોવાની આ એક રીત છે કે પી. એસ. પી. એ. એસ. એક્સ. પી. ટી. આઈ. એમ., કારણ કે વૈકલ્પિક ટ્યુરિંગ મશીન ઓછામાં ઓછું નિર્ણાયક ટ્યુરિંગ મશીન જેટલું શક્તિશાળી છે. EXPTIME-પૂર્ણ એક નિર્ણય સમસ્યા EXPTIME-પૂર્ણ છે જો તે EXPTIME માં હોય અને EXPTIME માં દરેક સમસ્યામાં બહુપદી-સમયની ઘણી-એક ઘટાડો હોય. બીજા શબ્દોમાં કહીએ તો, એક બહુપદી-સમય અલ્ગોરિધમ છે જે એક જ જવાબ સાથે એકના ઉદાહરણોને બીજાના ઉદાહરણોમાં પરિવર્તિત કરે છે. EXPTIME-પૂર્ણ સમસ્યાઓ EXPTIME માં સૌથી મુશ્કેલ સમસ્યાઓ તરીકે માનવામાં આવી શકે છે. નોંધ લો કે એન. પી. એ પી. ની બરાબર છે કે કેમ તે અજ્ઞાત હોવા છતાં, આપણે જાણીએ છીએ કે EXPTIME-પૂર્ણ સમસ્યાઓ પી. માં નથી; તે સાબિત થયું છે કે આ સમસ્યાઓ બહુપદી સમયમાં, સમય પદાનુક્રમ પ્રમેય દ્વારા ઉકેલી શકાતી નથી. કોમ્પ્યુટેબિલિટી થિયરીમાં, મૂળભૂત અનિર્ણાયક સમસ્યાઓમાંની એક અટકાવવાની સમસ્યા છેઃ તે નક્કી કરવું કે શું નિર્ધારક ટ્યુરિંગ મશીન (DTM) અટકી જાય છે. સૌથી મૂળભૂત EXPTIME-પૂર્ણ સમસ્યાઓમાંની એક આનું સરળ સંસ્કરણ છે, જે પૂછે છે કે શું DTM આપેલ ઇનપુટ પર મહત્તમ k પગલાંઓમાં અટકે છે. તે EXPTIME માં છે કારણ કે તુચ્છ સિમ્યુલેશન માટે O (k) સમયની જરૂર પડે છે, અને ઇનપુટ k ને O (log k) બિટ્સનો ઉપયોગ કરીને એન્કોડ કરવામાં આવે છે જે સિમુલેશનની ઘાતાંકીય સંખ્યાનું કારણ બને છે. તે EXPTIME-પૂર્ણ છે કારણ કે, આશરે કહીએ તો, આપણે તેનો ઉપયોગ એ નક્કી કરવા માટે કરી શકીએ છીએ કે EXPTIME સમસ્યાનું સમાધાન કરતું મશીન ઘાતાંકીય સંખ્યામાં પગલાંઓ સ્વીકારે છે કે નહીં; તે વધુ ઉપયોગ કરશે નહીં. યુનેરીમાં લખાયેલા પગલાંની સંખ્યા સાથે સમાન સમસ્યા પી-પૂર્ણ છે. EXPTIME-પૂર્ણ સમસ્યાઓના અન્ય ઉદાહરણોમાં સામાન્યીકૃત ચેસ, ચેકર્સ અથવા ગો (જાપાનીઝ કો નિયમો સાથે) માં સ્થિતિનું મૂલ્યાંકન કરવાની સમસ્યાનો સમાવેશ થાય છે. આ રમતોમાં EXPTIME-પૂર્ણ થવાની તક હોય છે કારણ કે રમતો બોર્ડના કદમાં ઘાતાંકીય હોય તેવી સંખ્યાબંધ ચાલ માટે ટકી શકે છે. ગો ઉદાહરણમાં, જાપાનીઝ કો નિયમ EXPTIME-પૂર્ણતા સૂચવવા માટે જાણીતો છે, પરંતુ રમત માટેના અમેરિકન અથવા ચીની નિયમો EXPTIME-પૂર્ણ છે કે કેમ તે જાણી શકાયું નથી (તેઓ PSPACE થી EXPSPACE સુધી હોઈ શકે છે). તેનાથી વિપરીત, સામાન્યીકૃત રમતો કે જે બોર્ડના કદમાં બહુપદી હોય તેવી સંખ્યાબંધ ચાલ માટે ટકી શકે છે તે ઘણીવાર PSPACE-પૂર્ણ હોય છે. એ જ ઝડપથી લાંબી રમતો માટે સાચું છે જેમાં બિન-પુનરાવર્તન સ્વચાલિત છે. મહત્વપૂર્ણ EXPTIME-પૂર્ણ સમસ્યાઓનો બીજો સમૂહ સંક્ષિપ્ત સર્કિટ સાથે સંબંધિત છે. સુસિંક્ટ સર્કિટ્સ એ સરળ મશીનો છે જેનો ઉપયોગ ઝડપથી ઓછી જગ્યામાં કેટલાક આલેખનું વર્ણન કરવા માટે થાય છે. તેઓ બે શિરોબિંદુ સંખ્યાઓને ઇનપુટ અને આઉટપુટ તરીકે સ્વીકારે છે, પછી ભલે તેમની વચ્ચે કોઈ ધાર હોય. ઘણી કુદરતી પી-પૂર્ણ ગ્રાફ સમસ્યાઓ માટે, જ્યાં ગ્રાફને સંલગ્નતા મેટ્રિક્સ જેવી કુદરતી રજૂઆતમાં વ્યક્ત કરવામાં આવે છે, તે જ સમસ્યાને સંક્ષિપ્ત સર્કિટ રજૂઆત પર હલ કરવી એ EXPTIME-પૂર્ણ છે, કારણ કે ઇનપુટ ઘાતાંકીય રીતે નાનું છે; પરંતુ આ માટે બિન-તુચ્છ સાબિતીની જરૂર છે, કારણ કે સંક્ષિપ્ત સર્કિટ માત્ર ગ્રાફના પેટા વર્ગનું વર્ણન કરી શકે છે. સંદર્ભો જટિલતા વર્ગો