Pseudo-Boolean function
ગણિત અને ઓપ્ટિમાઇઝેશનમાં, સ્યુડો-બુલિયન કાર્ય એ સ્વરૂપનું કાર્ય છે જ્યાં બુલિયન ડોમેન છે અને તે બિન-નકારાત્મક પૂર્ણાંક છે જેને કાર્યની એરીટી કહેવાય છે. બુલિયન ફંક્શન પછી એક વિશેષ કેસ છે, જ્યાં મૂલ્યો પણ 0 અથવા 1 સુધી મર્યાદિત હોય છે. રજૂઆતો કોઈપણ સ્યુડો-બુલિયન કાર્યને વિશિષ્ટ રીતે બહુ-રેખીય બહુપદી તરીકે લખી શકાય છેઃ સ્યુડો-બુલિયન કાર્યની ડિગ્રી એ આ રજૂઆતમાં બહુપદીની ડિગ્રી છે. ઘણી સેટિંગ્સમાં (દા. ત., સ્યુડો-બુલિયન કાર્યોના ફોરિયર વિશ્લેષણમાં), સ્યુડો-બુલિયન કાર્યને એક કાર્ય તરીકે જોવામાં આવે છે જે તેને મેપ કરે છે. ફરીથી આ કિસ્સામાં આપણે વિશિષ્ટ રીતે બહુ-રેખીય બહુપદી તરીકે લખી શકીએ છીએઃ અને ના ફોરિયર ગુણાંક ક્યાં છે. ઓપ્ટિમાઇઝેશન સ્યુડો-બુલિયન ફંક્શનને મિનિમાઇઝ કરવું (અથવા, સમકક્ષ રીતે, મહત્તમ કરવું) એ એન. પી.-હાર્ડ છે. આને સરળતાથી ફોર્મ્યુલેટિંગ દ્વારા જોઈ શકાય છે, ઉદાહરણ તરીકે, સ્યુડો-બુલિયન ફંક્શનને મહત્તમ કરવા તરીકે મહત્તમ કટ સમસ્યા. સબમોડ્યુલરિટી સબમોડ્યુલર સમૂહ કાર્યોને સ્યુડો-બુલિયન કાર્યોના વિશેષ વર્ગ તરીકે જોઈ શકાય છે, જે શરતની સમકક્ષ છે આ સ્યુડો-બુલિયન કાર્યોનો એક મહત્વપૂર્ણ વર્ગ છે, કારણ કે તેમને બહુપદી સમયમાં ઘટાડી શકાય છે. નોંધ લો કે સબમોડ્યુલર ફંક્શનનું લઘુતમકરણ એ પ્રસ્તુતિ ફોર્મ પર સ્વતંત્ર બહુપદી ઉકેલવા યોગ્ય સમસ્યા છે, દા. ત. પેસુડો-બુલિયન બહુપદીઓ, સબમોડ્યુલર ફંક્શનના મહત્તમકરણની વિરુદ્ધ જે એન. પી.-હાર્ડ છે, એલેક્ઝાન્ડર શ્રિજવર (2000). છતની દ્વૈતતા જો f એક દ્વિઘાત બહુપદી હોય, તો છતની દ્વૈતતા તરીકે ઓળખાતી વિભાવનાનો ઉપયોગ તેના લઘુત્તમ મૂલ્ય માટે નીચલી સીમા મેળવવા માટે કરી શકાય છે. છતની દ્વૈતતા ચલોનું આંશિક સોંપણી પણ પ્રદાન કરી શકે છે, જે બહુપદીમાં લઘુતમ મૂલ્યના કેટલાક મૂલ્યો સૂચવે છે. નીચલી સીમાઓ મેળવવાની ઘણી જુદી જુદી પદ્ધતિઓ વિકસાવવામાં આવી હતી જેને પાછળથી છતની દ્વૈતતા તરીકે ઓળખવામાં આવે છે તેની સમકક્ષ હોવાનું દર્શાવવામાં આવ્યું હતું. જો f ની ડિગ્રી 2 કરતા વધારે હોય, તો કોઈ પણ વ્યક્તિ હંમેશા વધારાના ચલ સાથે સમકક્ષ વર્ગાત્મક સમસ્યા મેળવવા માટે ઘટાડાનો ઉપયોગ કરી શકે છે. એક સંભવિત ઘટાડો એ છે કે અન્ય શક્યતાઓ પણ છે, ઉદાહરણ તરીકે, વિવિધ ઘટાડો વિવિધ પરિણામો તરફ દોરી જાય છે. ઉદાહરણ તરીકે નીચેની ઘન બહુપદી લોઃ પ્રથમ ઘટાડા પછી છતની દ્વૈતતાનો ઉપયોગ કરીને, આપણે-3 ની નીચી સીમા મેળવીએ છીએ અને ત્રણ ચલને કેવી રીતે સોંપવું તે અંગે કોઈ સંકેત નથી. બીજા ઘટાડાનો ઉપયોગ કરીને, આપણે-2 ની (ચુસ્ત) નીચલી સીમા અને દરેક ચલ (જે છે) ની શ્રેષ્ઠ સોંપણી મેળવીએ છીએ. બહુપદી સંકોચન અલ્ગોરિધમ્સ એક સ્યુડો-બુલિયન કાર્યને એકથી બીજાના મેપિંગ તરીકે ધ્યાનમાં લો. પછી ધારો કે દરેક ગુણાંક અભિન્ન છે. પછી પૂર્ણાંક માટે વધુ કે બરાબર છે તે નક્કી કરવાની સમસ્યા P એ NP-પૂર્ણ છે. તે સાબિત થાય છે કે બહુપદી સમયમાં આપણે કાં તો P ને હલ કરી શકીએ છીએ અથવા ચલની સંખ્યાને ઘટાડી શકીએ છીએ. પછી સાબિત કર્યું કે બહુપદી સમયમાં આપણે કાં તો P ને હલ કરી શકીએ છીએ અથવા ચલની સંખ્યાને ઘટાડી શકીએ છીએ. બુલિયન કાર્ય ક્વાડ્રેટિક સ્યુડો-બુલિયન ઓપ્ટિમાઇઝેશન નોંધો સંદર્ભો ગાણિતિક ઓપ્ટિમાઇઝેશન પણ જુઓ.