Structural complexity theory
કોમ્પ્યુટર વિજ્ઞાનના કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરીમાં, સ્ટ્રક્ચરલ કોમ્પ્લેક્સિટી થિયરી અથવા ફક્ત સ્ટ્રક્ચરલ કોમ્પ્લેક્સિટી એ વ્યક્તિગત સમસ્યાઓ અને અલ્ગોરિધમ્સની કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટીને બદલે કોમ્પ્લેક્સિટી ક્લાસનો અભ્યાસ છે. તેમાં વિવિધ જટિલતા વર્ગોના આંતરિક માળખા અને વિવિધ જટિલતા વર્ગો વચ્ચેના સંબંધો બંનેનું સંશોધન સામેલ છે. આ સિદ્ધાંત આ પ્રકારના પ્રથમ અને હજુ પણ સૌથી મહત્વપૂર્ણ પ્રશ્ન, પી = એન. પી. સમસ્યાને ઉકેલવાના (હજુ પણ નિષ્ફળ) પ્રયાસોના પરિણામે ઉભરી આવ્યો છે. મોટાભાગના સંશોધન એ ધારણા પર આધારિત છે કે પી એન. પી. ની બરાબર નથી અને વધુ દૂરગામી અનુમાન પર આધારિત છે કે જટિલતા વર્ગોની બહુપદી સમય પદાનુક્રમ અનંત છે. મહત્વપૂર્ણ પરિણામો સંકોચન પ્રમેય સંકોચન પ્રમેય એ ગણતરીપાત્ર કાર્યોની જટિલતા વિશેનો એક મહત્વપૂર્ણ પ્રમેય છે. આ પ્રમેય જણાવે છે કે ગણતરીપાત્ર સીમા સાથે કોઈ સૌથી મોટો જટિલતા વર્ગ અસ્તિત્વમાં નથી, જેમાં તમામ ગણતરીપાત્ર કાર્યો હોય. અવકાશ પદાનુક્રમ પ્રમેયો અવકાશ પદાનુક્રમ પ્રમેયો એ વિભાજન પરિણામો છે જે દર્શાવે છે કે નિર્ધારિત અને બિનનિર્ધારિત મશીનો બંને ચોક્કસ શરતોને આધિન વધુ જગ્યામાં (એસિમ્પ્ટોટિકલી) વધુ સમસ્યાઓ હલ કરી શકે છે. ઉદાહરણ તરીકે, એક નિર્ધારક ટ્યુરિંગ મશીન અવકાશ n કરતાં અવકાશ n માં વધુ નિર્ણય સમસ્યાઓ હલ કરી શકે છે. સમય માટે કંઈક અંશે નબળા એનાલોગસ પ્રમેયો સમય પદાનુક્રમના પ્રમેયો છે. સમય પદાનુક્રમ પ્રમેયો સમય પદાનુક્રમ પ્રમેયો ટ્યુરિંગ મશીનો પર સમય-મર્યાદિત ગણતરી વિશેના મહત્વપૂર્ણ નિવેદનો છે. અનૌપચારિક રીતે, આ પ્રમેયો કહે છે કે વધુ સમય આપવામાં આવે તો ટ્યુરિંગ મશીન વધુ સમસ્યાઓ હલ કરી શકે છે. ઉદાહરણ તરીકે, એવી સમસ્યાઓ છે જે n2 સમય સાથે ઉકેલી શકાય છે પરંતુ n સમય સાથે નહીં. વેલિયન્ટ-વઝીરાની પ્રમેય વેલિયન્ટ-વઝીરાની પ્રમેય એ કોમ્પ્યુટેશનલ જટિલતા સિદ્ધાંતમાં એક પ્રમેય છે. તે લેસ્લી વેલિયન્ટ અને વિજય વઝીરાની દ્વારા એન. પી. શીર્ષકવાળા તેમના પેપરમાં સાબિત કરવામાં આવ્યું હતું, જે 1986 માં પ્રકાશિત થયેલા અનન્ય ઉકેલો શોધવા જેટલું સરળ છે. આ પ્રમેય જણાવે છે કે જો અસંદિગ્ધ-SAT માટે બહુપદી સમય અલ્ગોરિધમ હોય, તો NP = RP. આ પુરાવો મુલ્મુલી-વઝીરાની અલગતા લેમ્મા પર આધારિત છે, જેનો ઉપયોગ પછીથી સૈદ્ધાંતિક કોમ્પ્યુટર વિજ્ઞાનમાં સંખ્યાબંધ મહત્વપૂર્ણ કાર્યક્રમો માટે કરવામાં આવ્યો હતો. સિપ્સર-લૉટમેન પ્રમેય સિપ્સર-લૉટમેન પ્રમેય અથવા સિપ્સર-ગેક્સ-લૉટમેન પ્રમેય જણાવે છે કે બાઉન્ડેડ-એરર પ્રોબેબિલિસ્ટિક પોલિનોમિયલ (BPP) સમય, બહુપદી સમય પદાનુક્રમમાં સમાયેલ છે, અને વધુ સ્પષ્ટ રીતે β2 β2 છે. 1970માં વોલ્ટર સેવિચ દ્વારા સાબિત કરાયેલ સેવિચનું પ્રમેય, નિર્ધારિત અને બિન-નિર્ધારિત અવકાશ જટિલતા વચ્ચેનો સંબંધ આપે છે. તે જણાવે છે કે કોઈપણ કાર્ય માટે, ટોડાના પ્રમેય ટોડાના પ્રમેય એ એક પરિણામ છે જે સિનોસુકે ટોડા દ્વારા તેમના પેપર "પીપી ઇઝ એઝ હાર્ડ એઝ ધ પોલિનોમિયલ-ટાઇમ હાયરાર્કી" (1991) માં સાબિત કરવામાં આવ્યું હતું અને તેને 1998 ગોડેલ પુરસ્કાર આપવામાં આવ્યો હતો. આ પ્રમેય જણાવે છે કે સમગ્ર બહુપદી પદાનુક્રમ PH એ PPP માં સમાયેલ છે; આ નજીકથી સંબંધિત નિવેદન સૂચવે છે, કે PH એ P#P માં સમાયેલ છે. ઇમ્મર્મન-ઝેલિપ્સનેયી પ્રમેય 1987માં નીલ ઇમ્મર્મન અને રોબર્ટ ઝેલિપ્સનેયી દ્વારા સ્વતંત્ર રીતે સાબિત કરવામાં આવ્યો હતો, જેના માટે તેઓએ 1995નો ગોડેલ પુરસ્કાર શેર કર્યો હતો. તેના સામાન્ય સ્વરૂપમાં પ્રમેય જણાવે છે કે NSPACE (s (n)) = સહ-NSPACE (s (n)) કોઈપણ કાર્ય માટે s (n) ≤ log n. પરિણામ સમાનરૂપે એન. એલ. = સહ-એન. એલ. તરીકે વર્ણવવામાં આવે છે; જો કે આ ખાસ કેસ છે જ્યારે s (n) = log n, તે પ્રમાણભૂત પેડિંગ દલીલ દ્વારા સામાન્ય પ્રમેય સૂચવે છે. પરિણામે બીજી એલ. બી. એ. સમસ્યાનું સમાધાન થયું. સંશોધન વિષયો આ ક્ષેત્રમાં સંશોધનની મુખ્ય દિશાઓમાં નીચેનાનો સમાવેશ થાય છેઃ જટિલતા વિશેની વિવિધ વણઉકેલાયેલી સમસ્યાઓથી ઉદભવેલી અસરોનો અભ્યાસ વર્ગ વિવિધ પ્રકારના સંસાધન-પ્રતિબંધિત ઘટાડાનો અભ્યાસ અને વિવિધ પ્રતિબંધોના પરિણામો અને સંગ્રહ અને માહિતીની પહોંચ માટેની પદ્ધતિઓનો સંબંધિત સંપૂર્ણ ભાષાઓનો અભ્યાસ સંદર્ભો