Valiant–Vazirani theorem
વેલિયન્ટ-વઝીરાની પ્રમેય એ કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરીમાં એક પ્રમેય છે જે જણાવે છે કે જો અસંદિગ્ધ-SAT માટે બહુપદી સમય અલ્ગોરિધમ હોય, તો NP = RP. તે લેસ્લી વેલિયન્ટ અને વિજય વઝીરાની દ્વારા એન. પી. શીર્ષકવાળા તેમના પેપરમાં સાબિત કરવામાં આવ્યું હતું, જે 1986 માં પ્રકાશિત થયેલા અનન્ય ઉકેલો શોધવા જેટલું સરળ છે. આ પુરાવો મુલ્મુલી-વઝીરાની-વઝીરાની અલગતા લેમ્મા પર આધારિત છે, જેનો ઉપયોગ પછીથી સૈદ્ધાંતિક કોમ્પ્યુટર વિજ્ઞાનમાં સંખ્યાબંધ મહત્વપૂર્ણ કાર્યક્રમો માટે કરવામાં આવ્યો હતો. વેલિયન્ટ-વઝીરાની પ્રમેય સૂચવે છે કે બુલિયન સંતોષકારક સમસ્યા, જે એન. પી.-પૂર્ણ છે, તે ગણતરીની દ્રષ્ટિએ મુશ્કેલ સમસ્યા છે, ભલે ઇનપુટ ઉદાહરણોમાં મહત્તમ એક સંતોષકારક સોંપણી હોવાનું વચન આપવામાં આવ્યું હોય. સાબિતી રૂપરેખા અસંદિગ્ધ-એસએટી એ નક્કી કરવાની વચનની સમસ્યા છે કે આપેલ બુલિયન સૂત્ર કે જેમાં મહત્તમ એક સંતોષકારક સોંપણી હોય તે અસંતોષકારક છે કે બરાબર એક સંતોષકારક સોંપણી છે. પ્રથમ કિસ્સામાં, અસંદિગ્ધ-SAT માટેના અલ્ગોરિધમનો અસ્વીકાર કરવો જોઈએ, અને બીજામાં તેણે સૂત્ર સ્વીકારવું જોઈએ. જો સૂત્રમાં એક કરતાં વધુ સંતોષકારક સોંપણી હોય, તો પછી અલ્ગોરિધમની વર્તણૂક પર કોઈ શરત નથી. વચનની સમસ્યા અસંદિગ્ધ-SAT એ બિનનિર્ધારણીય ટ્યુરિંગ મશીન દ્વારા નક્કી કરી શકાય છે જેમાં મહત્તમ એક સ્વીકાર્ય ગણતરી માર્ગ હોય છે. આ અર્થમાં, આ વચન સમસ્યા જટિલતા વર્ગ યુપી (જે સામાન્ય રીતે ફક્ત ભાષાઓ માટે વ્યાખ્યાયિત કરવામાં આવે છે) સાથે સંબંધિત છે. વેલિયન્ટ-વઝીરાની પ્રમેયના પુરાવાઓમાં SAT થી SAT માં સંભવિત ઘટાડાનો સમાવેશ થાય છે, જેમ કે સંભાવના સાથે, આઉટપુટ સૂત્રમાં મહત્તમ એક સંતોષકારક સોંપણી હોય છે, અને આમ અસંદિગ્ધ-SAT સમસ્યાના વચનને સંતોષે છે. વધુ સ્પષ્ટ રીતે કહીએ તો, ઘટાડો એ એક રેન્ડમાઇઝ્ડ બહુપદી-સમયનું અલ્ગોરિધમ છે જે બુલિયન સૂત્રમાં ચલ સાથે બુલિયન સૂત્રનો નકશો બનાવે છે જેથી દરેક સંતોષકારક સોંપણી પણ સંતોષાય, અને જો સંતોષકારક હોય, તો ઓછામાં ઓછી સંભાવના સાથે, એક અનન્ય સંતોષકારક સોંપણી હોય છે. ઘટાડાને બહુપદીની સંખ્યા ઘણી વખત ચલાવીને, દરેક વખતે તાજા સ્વતંત્ર રેન્ડમ બિટ્સ સાથે, આપણને સૂત્રો મળે છે. પસંદ કરવાથી, આપણે મેળવીએ છીએ કે ઓછામાં ઓછું એક સૂત્ર અનન્ય રીતે સંતોષકારક હોવાની સંભાવના ઓછામાં ઓછી જો સંતોષકારક હોય તો છે. આ ટ્યુરિંગને SAT થી અનમ્બીગ્યુઅસ-SAT માં ઘટાડો આપે છે કારણ કે અનમ્બીગ્યુઅસ-SAT માટે ધારેલા અલ્ગોરિધમનો ઉપયોગ કરી શકાય છે. પછી SAT ની સ્વ-ઘટાડાનો ઉપયોગ સંતોષકારક સોંપણીની ગણતરી કરવા માટે થઈ શકે છે, જો તે અસ્તિત્વમાં હોય તો. એકંદરે, આ સાબિત કરે છે કે એન. પી. = આર. પી. જો અસંદિગ્ધ-એસ. એ. ટી. ને આર. પી. માં ઉકેલી શકાય. ઘટાડાનો વિચાર સૂત્રની ઉકેલની જગ્યાને રેન્ડમ એફાઇન હાયપરપ્લેન સાથે છેદવાનો છે, જ્યાં રેન્ડમ રીતે સમાન રીતે પસંદ કરવામાં આવે છે. એક વૈકલ્પિક પુરાવો મુલ્મુલી, વઝીરાની અને વઝીરાની દ્વારા અલગ પાડેલા લેમ્મા પર આધારિત છે. તેઓ વધુ સામાન્ય સેટિંગને ધ્યાનમાં લે છે, અને અહીં સેટિંગ પર લાગુ થાય છે આ માત્ર એક અલગ થવાની સંભાવના આપે છે. સંદર્ભો માળખાકીય જટિલતા સિદ્ધાંત કોમ્પ્યુટેશનલ જટિલતા સિદ્ધાંતમાં પ્રમેયો