PSPACE-complete
કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરીમાં, નિર્ણયની સમસ્યા એ PSPACE-પૂર્ણ છે જો તેને ઇનપુટ લંબાઈ (બહુપદી જગ્યા) માં બહુપદી હોય તેવી મેમરીની માત્રાનો ઉપયોગ કરીને ઉકેલી શકાય અને જો બહુપદી જગ્યામાં ઉકેલી શકાય તેવી દરેક અન્ય સમસ્યાને બહુપદી સમયમાં તેમાં રૂપાંતરિત કરી શકાય. જે સમસ્યાઓ PSPACE-પૂર્ણ હોય તેને PSPACE માં સૌથી મુશ્કેલ સમસ્યાઓ તરીકે વિચારી શકાય છે, બહુપદી જગ્યામાં ઉકેલી શકાય તેવી નિર્ણય સમસ્યાઓનો વર્ગ, કારણ કે આવી કોઈપણ સમસ્યાના ઉકેલનો ઉપયોગ સરળતાથી PSPACE માં અન્ય કોઈપણ સમસ્યાને ઉકેલવા માટે થઈ શકે છે. PSPACE-પૂર્ણ તરીકે ઓળખાતી સમસ્યાઓમાં નિયમિત અભિવ્યક્તિઓ અને સંદર્ભ-સંવેદનશીલ વ્યાકરણના ગુણધર્મો નક્કી કરવા, પ્રમાણિત બુલિયન સૂત્રોનું સત્ય નક્કી કરવું, સંયુક્ત ઓપ્ટિમાઇઝેશન સમસ્યાઓના ઉકેલો વચ્ચે પગલું-દર-પગલા ફેરફારો અને ઘણી કોયડાઓ અને રમતોનો સમાવેશ થાય છે. એક સમસ્યાને PSPACE-પૂર્ણ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે જો તેને બહુપદી મેમરીનો ઉપયોગ કરીને ઉકેલી શકાય (તે PSPACE સાથે સંબંધિત છે) અને PSPACE માં દરેક સમસ્યાને બહુપદી સમયમાં આપેલ સમસ્યાના સમકક્ષ ઉદાહરણમાં રૂપાંતરિત કરી શકાય છે. PSPACE-પૂર્ણ સમસ્યાઓ વધુ પ્રખ્યાત જટિલતા વર્ગો P (બહુપદી સમય) અને NP (બિન-નિર્ધારિત બહુપદી સમય) ની બહાર હોવાની વ્યાપક શંકા છે, પરંતુ તે જાણી શકાયું નથી. તે જાણીતું છે કે તેઓ વર્ગ એન. સી. ની બહાર આવેલા છે, જે અત્યંત કાર્યક્ષમ સમાંતર અલ્ગોરિધમ્સ સાથેની સમસ્યાઓનો વર્ગ છે, કારણ કે એન. સી. માં સમસ્યાઓ ઇનપુટ કદના લઘુગણકમાં અવકાશ બહુપદીની માત્રામાં ઉકેલી શકાય છે, અને આટલી ઓછી જગ્યામાં ઉકેલી શકાય તેવી સમસ્યાઓનો વર્ગ અવકાશ પદાનુક્રમ દ્વારા પી. એસ. પી. એ. સી. ઈ. માં સખત રીતે સમાયેલ છે. સામાન્ય રીતે પી. એસ. પી. એ. સી. ઈ.-પૂર્ણતાને વ્યાખ્યાયિત કરવામાં જે પરિવર્તનોનો વિચાર કરવામાં આવે છે તે બહુપદી-સમયના ઘણા-એક ઘટાડા છે, પરિવર્તન જે એક પ્રકારની સમસ્યાના એક ઉદાહરણને અલગ પ્રકારની સમસ્યાના સમકક્ષ એક ઉદાહરણમાં લે છે. જો કે, ટ્યુરિંગ ઘટાડાનો ઉપયોગ કરીને સંપૂર્ણતાને વ્યાખ્યાયિત કરવી પણ શક્ય છે, જેમાં એક સમસ્યાને અન્ય સમસ્યા માટે સબરૂટિન પર બહુપદી સંખ્યામાં કોલ કરીને ઉકેલી શકાય છે. તે જાણીતું નથી કે આ બે પ્રકારના ઘટાડા PSPACE-પૂર્ણ સમસ્યાઓના વિવિધ વર્ગો તરફ દોરી જાય છે કે કેમ. અન્ય પ્રકારના ઘટાડા, જેમ કે ઘણા-એક ઘટાડા કે જે હંમેશા રૂપાંતરિત ઇનપુટની લંબાઈમાં વધારો કરે છે, તે પણ ધ્યાનમાં લેવામાં આવ્યા છે. પી. એસ. પી. એ. સી. ઈ.-પૂર્ણ સમૂહો માટે બર્મન-હાર્ટમેનિસ અનુમાનની એક આવૃત્તિ જણાવે છે કે આવા તમામ સમૂહો એકસરખા દેખાય છે, એ અર્થમાં કે તે બધાને બહુપદી-સમયના દ્વિભાજન દ્વારા એક બીજામાં રૂપાંતરિત કરી શકાય છે. ઉદાહરણો ઔપચારિક ભાષાઓ નિયમિત અભિવ્યક્તિ આપવામાં આવે છે, તે નક્કી કરે છે કે તે તેના મૂળાક્ષર પર દરેક શબ્દમાળા ઉત્પન્ન કરે છે કે કેમ તે PSPACE-પૂર્ણ છે. પ્રથમ જાણીતી પી. એસ. પી. એ. સી. ઈ.-પૂર્ણ સમસ્યા નિર્ધારક સંદર્ભ-સંવેદનશીલ વ્યાકરણ માટે શબ્દ સમસ્યા હતી. સંદર્ભ-સંવેદનશીલ વ્યાકરણ માટે સમસ્યા શબ્દમાં, વ્યક્તિને વ્યાકરણના પરિવર્તનોનો સમૂહ આપવામાં આવે છે જે વાક્યની લંબાઈને વધારી શકે છે, પરંતુ ઘટાડી શકતા નથી, અને તે નક્કી કરવા માંગે છે કે આ પરિવર્તન દ્વારા આપેલ વાક્ય ઉત્પન્ન કરી શકાય છે કે કેમ. "નિર્ધારણવાદ" ની તકનીકી સ્થિતિ (આશરે સૂચવે છે કે દરેક પરિવર્તન તે સ્પષ્ટ કરે છે કે તેનો ઉપયોગ કરવામાં આવ્યો હતો) એ સુનિશ્ચિત કરે છે કે આ પ્રક્રિયાને બહુપદી જગ્યામાં ઉકેલી શકાય છે, અને દર્શાવ્યું કે રેખીય જગ્યામાં ગણતરી કરી શકાય તેવા દરેક (સંભવતઃ બિન-નિર્ધારિત) પ્રોગ્રામને સંદર્ભ-સંવેદનશીલ વ્યાકરણના પદચ્છેદનમાં રૂપાંતરિત કરી શકાય છે, જે રીતે નિર્ધારણવાદને જાળવી રાખે છે. 1970માં, સેવિચનું પ્રમેય દર્શાવે છે કે પી. એસ. પી. એ. સી. ઈ. બિનનિર્ધારણીયતા હેઠળ બંધ છે, જે સૂચવે છે કે બિન-નિર્ધારિત સંદર્ભ-સંવેદનશીલ વ્યાકરણ પણ પી. એસ. પી. એ. સી. ઈ. માં છે. તર્ક એક પ્રમાણભૂત પી. એસ. પી. એ. સી. ઈ.-પૂર્ણ સમસ્યા, જેનો ઉપયોગ અન્ય ઘણા પી. એસ. પી. એ. સી. ઈ.-પૂર્ણતાના પરિણામોમાં થાય છે, તે માત્રાત્મક બુલિયન સૂત્ર સમસ્યા છે, જે બુલિયન સંતોષકારક સમસ્યાનું સામાન્યીકરણ છે. માત્રાત્મક બુલિયન સૂત્ર સમસ્યા બુલિયન અભિવ્યક્તિને ઇનપુટ તરીકે લે છે, જેમાં તેના તમામ ચલોનું પ્રમાણ સાર્વત્રિક અથવા અસ્તિત્વમાં હોય છે, ઉદાહરણ તરીકેઃ સમસ્યાનું ઉત્પાદન એ માત્રાત્મક અભિવ્યક્તિનું મૂલ્ય છે. આ મૂલ્ય શોધવું એ PSPACE-પૂર્ણ છે. પુનઃરૂપરેખાંકન પુનઃરૂપરેખાંકન સમસ્યાઓ સંયુક્ત સમસ્યાના ઉકેલોની સ્થિતિ જગ્યાના જોડાણની ચિંતા કરે છે. દાખલા તરીકે, આલેખના બે 4-રંગોને એક સમયે એક શિરોબિંદુના રંગમાં ફેરફાર કરતી ચાલ દ્વારા એકબીજા સાથે જોડી શકાય છે કે કેમ તેનું પરીક્ષણ કરવું, દરેક તબક્કે માન્ય 4-રંગ જાળવી રાખવો, એ PSPACE-પૂર્ણ છે, તેમ છતાં 3-રંગ માટે સમાન સમસ્યા બહુપદી સમયમાં ઉકેલી શકાય છે. પુનઃરૂપરેખાંકન સમસ્યાઓનો બીજો પરિવાર, જેનો ઉપયોગ આ ક્ષેત્રમાં અન્ય ઘણી સમસ્યાઓના પી. એસ. પી. એ. સી. ઈ.-પૂર્ણતાના પુરાવા માટેના આધાર તરીકે જથ્થાત્મક બુલિયન સૂત્રોની જેમ જ થાય છે, તેમાં બિનનિર્ધારણીય અવરોધ તર્કનો સમાવેશ થાય છે, જેમાં સ્થિતિઓ અવરોધ આલેખની દિશાઓ છે, જે દરેક શિરોબિંદુ પર કેટલી ધાર અંદરની તરફ હોવી જોઈએ તેના પર ચોક્કસ અવરોધોને આધિન છે, અને જેમાં રાજ્યમાંથી રાજ્યમાં ચાલ એક ધારની દિશા ઉલટાવી દે છે. કોયડાઓ અને રમતો માત્રાત્મક બુલિયન સૂત્રની સમસ્યાનું અર્થઘટન બે ખેલાડીઓ, ચકાસણી કરનાર અને ખોટી સાબિત કરનાર દ્વારા રમત તરીકે કરી શકાય છે. ખેલાડીઓ એવી ચાલ કરે છે જે ક્વોન્ટિફાઇડ વેરિયેબલ્સ માટે મૂલ્યો ભરે છે, જે ક્રમમાં તેઓ નેસ્ટેડ હોય છે, જેમાં વેરિફાયર અસ્તિત્વમાં ક્વોન્ટિફાઇડ વેરિયેબલ્સ ભરે છે અને સાર્વત્રિક રીતે ક્વોન્ટિફાઇડ વેરિયેબલ્સ ભરે છે; જો ભરેલું સૂત્ર સાચું પડે તો વેરિફાયર દ્વારા રમત જીતી લેવામાં આવે છે, અને અન્યથા ફોલસિફાયર દ્વારા. માત્રાત્મક સૂત્ર ત્યારે જ સાચું છે જ્યારે ચકાસણી કરનાર પાસે જીતવાની વ્યૂહરચના હોય. તેવી જ રીતે, અન્ય ઘણી સંયુક્ત રમતોના વિજેતા અથવા હારનારને નક્કી કરવાની સમસ્યા PSPACE-પૂર્ણ હોવાનું બહાર આવ્યું છે. જે રમતો પી. એસ. પી. એ. સી. ઇ.-પૂર્ણ હોય તેના ઉદાહરણો (જ્યારે સામાન્યીકૃત કરવામાં આવે છે જેથી તેઓ બોર્ડ પર રમી શકાય) હેક્સ અને રિવર્સી રમતો છે. કેટલીક અન્ય સામાન્યીકૃત રમતો, જેમ કે ચેસ, ચેકર્સ (ડ્રાફ્ટ્સ) અને ગો EXPTIME-પૂર્ણ છે કારણ કે બે સંપૂર્ણ ખેલાડીઓ વચ્ચેની રમત ખૂબ લાંબી હોઈ શકે છે, તેથી તેઓ PSPACE માં હોવાની શક્યતા નથી. પરંતુ જો ચાલની સંખ્યા પર બંધાયેલ બહુપદી લાગુ કરવામાં આવે તો તેઓ PSPACE-પૂર્ણ બની જશે. એક જ ખેલાડી દ્વારા ભજવવામાં આવતી કોયડાઓ માટે પણ શક્ય છે કે તે PSPACE-પૂર્ણ હોય. આને ઘણીવાર પુનઃરૂપરેખાંકન સમસ્યાઓ તરીકે અર્થઘટન કરી શકાય છે, અને તેમાં સોલિટેયર રમતો રશ અવર, માહજોંગ, એટોમિક્સ અને સોકોબાન અને યાંત્રિક કમ્પ્યુટર ટ્યુરિંગ ટમ્બલનો સમાવેશ થાય છે. પી. એસ. પી. એ. સી. ઈ.-પૂર્ણતા ઇનપુટ કદના કાર્ય તરીકે જટિલતા પર આધારિત છે, જેમ જેમ મર્યાદા બંધાયેલ વગર વધે છે. પરંપરાગત બોર્ડ પર ચેસ જેવી મર્યાદિત સંખ્યામાં સ્થાનો ધરાવતી કોયડાઓ અથવા રમતો PSPACE-પૂર્ણ ન હોઈ શકે, કારણ કે તેમને ખૂબ મોટા લુકઅપ ટેબલનો ઉપયોગ કરીને સતત સમય અને જગ્યામાં ઉકેલી શકાય છે. આ રમતોની પી. એસ. પી. એ. સી. ઈ.-પૂર્ણ આવૃત્તિઓ તૈયાર કરવા માટે, તેમાં એવી રીતે ફેરફાર કરવો આવશ્યક છે કે જેથી તેમની સ્થિતિઓની સંખ્યા અમર્યાદિત રહે, જેમ કે તેમને બોર્ડ પર રમીને. કેટલાક કિસ્સાઓમાં, જેમ કે ચેસ માટે, આ વિસ્તરણ કૃત્રિમ છે. સંદર્ભો વધુ વાંચન જટિલતા વર્ગો