Circuit satisfiability problem
સૈદ્ધાંતિક કોમ્પ્યુટર વિજ્ઞાનમાં, સર્કિટ સંતોષકારકતાની સમસ્યા (જેને CIRCUIT-SAT, સર્કિટસેટ, CSAT, વગેરે તરીકે પણ ઓળખવામાં આવે છે) આપેલ બુલિયન સર્કિટમાં તેના ઇનપુટ્સની સોંપણી છે કે કેમ તે નક્કી કરવાની નિર્ણય સમસ્યા છે જે આઉટપુટને સાચું બનાવે છે. બીજા શબ્દોમાં કહીએ તો, તે પૂછે છે કે શું આપેલ બુલિયન સર્કિટના ઇનપુટ્સને સતત 1 અથવા 0 પર સેટ કરી શકાય છે કે જેથી સર્કિટ 1 આઉટપુટ આપે. જો એમ હોય તો, સર્કિટને સંતોષકારક કહેવામાં આવે છે. નહિંતર, સર્કિટને અસંતોષકારક કહેવામાં આવે છે. જમણી બાજુની આકૃતિમાં, ડાબી સર્કિટને બંને ઇનપુટ્સને 1 સેટ કરીને સંતુષ્ટ કરી શકાય છે, પરંતુ જમણી સર્કિટ અસંતોષકારક છે. સર્કિટસેટ બુલિયન સંતોષકારક સમસ્યા (એસએટી) સાથે નજીકથી સંબંધિત છે, અને તેવી જ રીતે, એનપી-પૂર્ણ હોવાનું સાબિત થયું છે. તે એક પ્રોટોટાઇપિકલ એન. પી.-પૂર્ણ સમસ્યા છે; કૂક-લેવિન પ્રમેય કેટલીકવાર એસ. એ. ટી. ને બદલે સર્કિટસેટ પર સાબિત થાય છે, અને પછી સર્કિટસેટને તેમની એન. પી.-પૂર્ણતા સાબિત કરવા માટે અન્ય સંતોષકારક સમસ્યાઓમાં ઘટાડી શકાય છે. મનસ્વી દ્વિસંગી દરવાજા ધરાવતી પરિપથની સંતોષકારકતા સમયસર નક્કી કરી શકાય છે. એન. પી.-પૂર્ણતાનો પુરાવો સર્કિટ અને ઇનપુટ્સના સંતોષકારક સમૂહને જોતાં, દરેક ગેટના આઉટપુટની ગણતરી સતત સમયે કરી શકાય છે. તેથી, સર્કિટનું આઉટપુટ બહુપદી સમયમાં ચકાસી શકાય તેવું છે. આમ સર્કિટ SAT જટિલતા વર્ગ NP સાથે સંબંધિત છે. એન. પી.-કઠોરતા દર્શાવવા માટે, 3એસ. એ. ટી. થી સર્કિટ એસ. એ. ટી. માં ઘટાડો કરવો શક્ય છે. ધારો કે મૂળ 3SAT સૂત્રમાં ચલ અને સંચાલકો (AND, OR, NOT) છે. સર્કિટની રચના એવી રીતે કરો કે જેમાં દરેક ચલને અનુરૂપ ઇનપુટ અને દરેક સંચાલકને અનુરૂપ દ્વાર હોય. 3એસએટી સૂત્ર અનુસાર દરવાજાને જોડો. દાખલા તરીકે, જો 3SAT સૂત્ર સર્કિટમાં 3 ઇનપુટ્સ હશે, તો એક AND, એક OR, અને એક NOT ગેટ હશે. અનુરૂપ ઇનપુટ AND ગેટ પર મોકલતા પહેલા ઊંધું કરવામાં આવશે અને AND ગેટનું આઉટપુટ OR ગેટ પર મોકલવામાં આવશે અને નોંધ લો કે 3SAT સૂત્ર ઉપર રચાયેલ સર્કિટની સમકક્ષ છે, તેથી તેમનું આઉટપુટ સમાન ઇનપુટ માટે સમાન છે. તેથી, જો 3SAT સૂત્ર સંતોષકારક સોંપણી ધરાવે છે, તો અનુરૂપ સર્કિટ 1 નું આઉટપુટ આપશે, અને ઊલટું. તેથી, આ એક માન્ય ઘટાડો છે, અને સર્કિટ SAT એ NP-હાર્ડ છે. આ એ સાબિતીને પૂર્ણ કરે છે કે સર્કિટ SAT એ NP-પૂર્ણ છે. પ્રતિબંધિત પ્રકારો અને સંબંધિત સમસ્યાઓ પ્લાનર સર્કિટ (SAT) ધારો કે આપણને પ્લાનર બુલિયન સર્કિટ (એટલે કે. એક બુલિયન સર્કિટ કે જેનો અંતર્ગત આલેખ સમતલીય હોય છે) જેમાં બરાબર બે ઇનપુટ્સ સાથે માત્ર NAND ગેટ્સ હોય છે. પ્લાનર સર્કિટ SAT એ નક્કી કરવાની નિર્ણય સમસ્યા છે કે શું આ સર્કિટમાં તેના ઇનપુટ્સની સોંપણી છે કે જે આઉટપુટને સાચું બનાવે છે. આ સમસ્યા એન. પી.-પૂર્ણ છે. વધુમાં, જો નિયંત્રણો બદલવામાં આવે છે જેથી સર્કિટમાં કોઈપણ દ્વાર NOR દ્વાર હોય, તો પરિણામી સમસ્યા NP-પૂર્ણ રહે છે. યુ. એન. એસ. એ. ટી. સર્કિટ યુ. એન. એસ. એ. ટી. એ નક્કી કરવાની નિર્ણયની સમસ્યા છે કે આપેલ બુલિયન સર્કિટ તેના ઇનપુટ્સની તમામ સંભવિત સોંપણીઓ માટે ખોટું આઉટપુટ આપે છે કે કેમ. આ સર્કિટ SAT સમસ્યાનું પૂરક છે, અને તેથી તે સહ-NP-પૂર્ણ છે. સર્કિટસેટ અથવા તેના પ્રકારોમાંથી સર્કિટસેટમાં ઘટાડાનો ઉપયોગ ચોક્કસ સમસ્યાઓની એન. પી.-કઠોરતા દર્શાવવા માટે થઈ શકે છે, અને આપણને દ્વિ-રેલ અને દ્વિસંગી તર્ક ઘટાડાનો વિકલ્પ પૂરો પાડે છે. આવા ઘટાડાને જે ઉપકરણો બનાવવાની જરૂર છે તે છેઃ એક વાયર ગેજેટ. આ ગેજેટ સર્કિટમાં વાયરનું અનુકરણ કરે છે. એક વિભાજિત ગેજેટ. આ ગેજેટ ખાતરી આપે છે કે તમામ આઉટપુટ વાયરનું મૂલ્ય ઇનપુટ વાયર જેટલું જ છે. સર્કિટના દરવાજાનું અનુકરણ કરતા ગેજેટ્સ. એક સાચું ટર્મિનેટર ગેજેટ. આ ગેજેટનો ઉપયોગ સમગ્ર સર્કિટના આઉટપુટને ટ્રુ બનાવવા માટે કરવામાં આવે છે. એક વળાંક ગેજેટ. આ ગેજેટ આપણને જરૂરિયાત મુજબ વાયરને યોગ્ય દિશામાં રીડાયરેક્ટ કરવાની મંજૂરી આપે છે. ક્રોસઓવર ગેજેટ. આ ગેજેટ આપણને ક્રિયાપ્રતિક્રિયા કર્યા વિના બે વાયરને એકબીજાને પાર કરવાની મંજૂરી આપે છે. માઇન્સવીપર અનુમાન સમસ્યા આ સમસ્યા પૂછે છે કે શું માઇન્સવીપર બોર્ડ આપવામાં આવેલા તમામ બોમ્બને શોધવાનું શક્ય છે. સર્કિટ યુ. એન. એસ. એ. ટી. સમસ્યામાં ઘટાડા દ્વારા તે સી. ઓ. એન. પી.-પૂર્ણ સાબિત થયું છે. આ ઘટાડા માટે બનાવવામાં આવેલા ઉપકરણો છેઃ વાયર, સ્પ્લિટ, એન્ડ અને નોટ ગેટ્સ અને ટર્મિનેટર. આ ઉપકરણો અંગે ત્રણ નિર્ણાયક અવલોકનો છે. પ્રથમ, સ્પ્લિટ ગેજેટનો ઉપયોગ નોટ ગેજેટ અને ટર્ન ગેજેટ તરીકે પણ થઈ શકે છે. બીજું, એન્ડ અને નોટ ગેજેટ્સનું નિર્માણ પૂરતું છે, કારણ કે એકસાથે તેઓ સાર્વત્રિક NAND ગેટનું અનુકરણ કરી શકે છે. છેવટે, XOR ને અમલમાં મૂકવા માટે ત્રણ NAND ને આંતરછેદ-મુક્ત બનાવી શકાય છે, અને XOR ક્રોસઓવર બનાવવા માટે પૂરતું હોવાથી, આ આપણને જરૂરી ક્રોસઓવર ગેજેટ આપે છે. ત્સેટીન પરિવર્તન એ સર્કિટ-એસએટીથી એસએટીમાં સીધો ઘટાડો છે. જો સર્કિટ સંપૂર્ણપણે 2-ઇનપુટ NAND ગેટ્સ (બુલિયન ઓપરેટર્સનો કાર્યાત્મક રીતે પૂર્ણ સમૂહ) માંથી બનાવવામાં આવી હોય તો પરિવર્તનનું વર્ણન કરવું સરળ છેઃ સર્કિટમાં દરેક નેટને ચલ સોંપો, પછી દરેક NAND ગેટ માટે, કન્જેક્ટિવ નોર્મલ ફોર્મ ક્લોઝ (v1⁄v3) ′ (v2⁄v3) ′ (̃v1⁄v2⁄v3) બનાવો, જ્યાં v1 અને v2 એ NAND ગેટના ઇનપુટ્સ છે અને v3 એ આઉટપુટ છે. આ કલમો ત્રણ ચલ વચ્ચેના સંબંધને સંપૂર્ણપણે વર્ણવે છે. તમામ દરવાજામાંથી કલમોને સર્કિટના આઉટપુટ વેરિયેબલને સાચું હોવાનું અવરોધિત કરતી વધારાની કલમ સાથે જોડવાથી ઘટાડો પૂર્ણ થાય છે; તમામ અવરોધોને સંતોષતા ચલોનું સોંપણી ત્યારે જ અસ્તિત્વમાં હોય છે જ્યારે મૂળ સર્કિટ સંતોષકારક હોય, અને કોઈપણ ઉકેલ એ સર્કિટ આઉટપુટ 1 બનાવે તેવા ઇનપુટ્સ શોધવાની મૂળ સમસ્યાનું સમાધાન હોય. તેનાથી વિપરીત-કે SAT સર્કિટ-SAT માટે ઘટાડી શકાય તેવું છે-બુલિયન સૂત્રને સર્કિટ તરીકે ફરીથી લખીને અને તેને હલ કરીને તુચ્છ રીતે અનુસરે છે. સર્કિટ વેલ્યુ પ્રોબ્લેમ સ્ટ્રક્ચર્ડ સર્કિટ સેટીફાયેબિલિટી સેટીફાયેબિલિટી પ્રોબ્લેમ સંદર્ભો એન. પી.-પૂર્ણ સમસ્યાઓ કોમ્પ્યુટેશનલ સમસ્યાઓ કમ્પ્યુટેબિલિટી થિયરી પણ જુઓ.