Fagin's theorem
ફેગિનનો પ્રમેય વર્ણનાત્મક જટિલતા સિદ્ધાંતનું સૌથી જૂનું પરિણામ છે, જે કોમ્પ્યુટેશનલ જટિલતા સિદ્ધાંતની એક શાખા છે, જે જટિલતા વર્ગોને તે સમસ્યાઓના ઉકેલ માટે અલ્ગોરિધમ્સના વર્તનને બદલે તેમની સમસ્યાઓના તર્ક-આધારિત વર્ણનની દ્રષ્ટિએ વર્ગીકૃત કરે છે. આ પ્રમેય જણાવે છે કે અસ્તિત્વના બીજા ક્રમના તર્કમાં વ્યક્ત કરી શકાય તેવા તમામ ગુણધર્મોનો સમૂહ ચોક્કસપણે જટિલતા વર્ગ એન. પી. છે. તે રોનાલ્ડ ફેગિન દ્વારા 1973 માં તેમના ડોક્ટરલ થીસીસમાં સાબિત કરવામાં આવ્યું હતું, અને તેમના 1974 ના પેપરમાં દેખાય છે. બીજા ક્રમના સૂત્ર દ્વારા જરૂરી યોગ્યતા (એક દિશામાં) માં સુધારો કરવામાં આવ્યો હતો, અને ગ્રાન્ડજેનના કેટલાક પરિણામોએ બિનનિર્ધારિત રેન્ડમ-એક્સેસ મશીનો પર સખત સીમા પૂરી પાડી છે. સાબિતી ફેગિનના 1974 ના પેપર ઉપરાંત, પ્રમેયનો વિગતવાર પુરાવો પૂરો પાડે છે. તે બતાવવું સરળ છે કે દરેક અસ્તિત્વના બીજા ક્રમના સૂત્રને એન. પી. માં ઓળખી શકાય છે, બિનનિર્ધારિત રીતે તમામ અસ્તિત્વના લાયક ચલોનું મૂલ્ય પસંદ કરીને, તેથી સાબિતીનો મુખ્ય ભાગ એ બતાવવાનો છે કે એન. પી. માં દરેક ભાષાને અસ્તિત્વના બીજા ક્રમના સૂત્ર દ્વારા વર્ણવી શકાય છે. આવું કરવા માટે, ગણતરીની ઝાંખીને મનસ્વી રીતે પસંદ કરવા માટે બીજા ક્રમના અસ્તિત્વના પરિમાણોનો ઉપયોગ કરી શકાય છે. વધુ વિગતવાર, બિન-નિર્ધારિત ટ્યુરિંગ મશીનના એક્ઝેક્યુશન ટ્રેસના દરેક ટાઇમસ્ટેપ માટે, આ ઝાંખી ટ્યુરિંગ મશીનની સ્થિતિ, ટેપમાં તેની સ્થિતિ, દરેક ટેપ સેલની સામગ્રી અને તે તબક્કે મશીન કઈ બિન-નિર્ધારિત પસંદગી કરે છે તે એન્કોડ કરે છે. ફર્સ્ટ-ઓર્ડર ફોર્મ્યુલા આ એન્કોડેડ માહિતીને મર્યાદિત કરી શકે છે જેથી તે માન્ય એક્ઝેક્યુશન ટ્રેસનું વર્ણન કરે, જેમાં ટેપ સમાવિષ્ટો અને ટ્યુરિંગ મશીનની સ્થિતિ અને દરેક ટાઇમસ્ટેપ પરની સ્થિતિ અગાઉના ટાઇમસ્ટેપને અનુસરે છે. સાબિતીમાં ઉપયોગમાં લેવાતો મુખ્ય સિદ્ધાંત એ છે કે બ્રહ્માંડના સંબંધ તરીકે લંબાઈના રેખીય ક્રમને (જેમ કે કોઈપણ સમયે ટાઇમસ્ટેપ્સ અને ટેપ સમાવિષ્ટોના રેખીય ક્રમ) એન્કોડ કરવો શક્ય છે. આ હાંસલ કરવાની એક રીત એ છે કે રેખીય ક્રમ પસંદ કરવો અને પછી સંદર્ભ સાથે શબ્દકોષીય ક્રમ તરીકે વ્યાખ્યાયિત કરવું.