Circuit satisfiability problem
கோட்பாட்டு கணினி அறிவியலில், சுற்று திருப்திகரமான சிக்கல் (CIRCUIT-SAT, சர்க்யூட்ஷாட், CSAT போன்றவை என்றும் அழைக்கப்படுகிறது) கொடுக்கப்பட்ட பூலியன் சுற்றுக்கு அதன் உள்ளீடுகளின் ஒதுக்கீடு உள்ளதா என்பதை தீர்மானிப்பதற்கான முடிவு சிக்கலாகும், இது வெளியீட்டை உண்மையாக்குகிறது. வேறு வார்த்தைகளில் கூறுவதானால், கொடுக்கப்பட்ட பூலியன் சுற்றுக்கான உள்ளீடுகளை 1 அல்லது 0 ஆக தொடர்ந்து அமைக்க முடியுமா என்று அது கேட்கிறது, இதனால் சுற்று 1 ஐ வெளியிடுகிறது. அப்படியானால், சுற்று திருப்திகரமானதாக அழைக்கப்படுகிறது. இல்லையெனில், சுற்று திருப்தியற்றது என்று அழைக்கப்படுகிறது. வலதுபுறத்தில் உள்ள படத்தில், இரண்டு உள்ளீடுகளையும் 1 ஆக அமைப்பதன் மூலம் இடது சுற்றுவட்டத்தை திருப்திப்படுத்தலாம், ஆனால் வலது சுற்று திருப்தியளிக்காது. சர்க்யூட்எஸ்ஏடி பூலியன் திருப்திகரமான சிக்கலுடன் (எஸ்ஏடி) நெருக்கமாக தொடர்புடையது, அதேபோல், என். பி-முழுமையானது என்று நிரூபிக்கப்பட்டுள்ளது. இது ஒரு முன்மாதிரி NP-முழுமையான சிக்கல்; குக்-லெவின் தேற்றம் சில நேரங்களில் SAT க்கு பதிலாக சர்க்யூட் SAT இல் நிரூபிக்கப்படுகிறது, பின்னர் சர்க்யூட் SAT ஐ அவற்றின் NP-முழுமையை நிரூபிக்க மற்ற திருப்திகரமான சிக்கல்களுக்கு குறைக்கலாம். தன்னிச்சையான பைனரி வாயில்களைக் கொண்ட ஒரு சுற்றுகளின் திருப்தியை சரியான நேரத்தில் தீர்மானிக்க முடியும். NP-முழுமையின் சான்று ஒரு சுற்று மற்றும் திருப்திகரமான உள்ளீடுகளின் தொகுப்பைக் கொடுத்தால், ஒவ்வொரு வாயிலின் வெளியீட்டையும் நிலையான நேரத்தில் கணக்கிட முடியும். எனவே, சுற்றுகளின் வெளியீடு பல்லுறுப்புக்கோவை நேரத்தில் சரிபார்க்கக்கூடியது. எனவே சர்க்யூட் SAT சிக்கலான வகுப்பு NP க்கு சொந்தமானது. NP-கடினத்தன்மையைக் காட்ட, 3SAT இலிருந்து சர்க்யூட் SAT க்கு குறைப்பை உருவாக்க முடியும். அசல் 3SAT சூத்திரத்தில் மாறிகள் மற்றும் ஆபரேட்டர்கள் (AND, OR, NOT) உள்ளன என்று வைத்துக்கொள்வோம். ஒவ்வொரு மாறிக்கும் பொருந்தக்கூடிய உள்ளீடு மற்றும் ஒவ்வொரு ஆபரேட்டருக்கும் பொருந்தக்கூடிய ஒரு கேட்டைக் கொண்டிருக்கும் வகையில் ஒரு சுற்றுவட்டத்தை வடிவமைக்கவும். 3SAT சூத்திரத்தின் படி வாயில்களை இணைக்கவும். எடுத்துக்காட்டாக, 3சாட் சூத்திரம் சர்க்யூட் என்றால் 3 உள்ளீடுகள் இருக்கும், ஒன்று AND, ஒன்று OR, மற்றும் ஒன்று NOT கேட். தொடர்புடைய உள்ளீடு ஒரு AND வாயிலுக்கு அனுப்புவதற்கு முன்பு தலைகீழாக இருக்கும், மேலும் AND வாயிலின் வெளியீடு ஒரு OR வாயிலுக்கு அனுப்பப்படும், 3SAT சூத்திரம் மேலே வடிவமைக்கப்பட்ட சுற்றுக்கு சமம் என்பதைக் கவனியுங்கள், எனவே அவற்றின் வெளியீடு அதே உள்ளீட்டிற்கு ஒரே மாதிரியாக இருக்கும். எனவே, 3SAT சூத்திரம் திருப்திகரமான வேலையைக் கொண்டிருந்தால், அதனுடன் தொடர்புடைய சுற்று 1 ஐ வெளியிடும், மேலும் நேர்மாறாகவும் இருக்கும். எனவே, இது ஒரு செல்லுபடியாகும் குறைப்பு, மற்றும் சர்க்யூட் SAT NP-கடினமானது. சர்க்யூட் SAT NP-முழுமையானது என்பதற்கான ஆதாரத்தை இது நிறைவு செய்கிறது. கட்டுப்படுத்தப்பட்ட மாறுபாடுகள் மற்றும் தொடர்புடைய சிக்கல்கள் பிளானர் சர்க்யூட் எஸ்ஏடி நமக்கு ஒரு பிளானர் பூலியன் சர்க்யூட் (அதாவது. ஒரு பூலியன் சுற்று, அதன் அடிப்படை வரைபடம் சமதளமாக உள்ளது) சரியாக இரண்டு உள்ளீடுகளுடன் NAND வாயில்களை மட்டுமே கொண்டுள்ளது. பிளானர் சர்க்யூட் SAT என்பது இந்த சர்க்யூட் அதன் உள்ளீடுகளின் ஒரு ஒதுக்கீட்டைக் கொண்டிருக்கிறதா என்பதை தீர்மானிப்பதற்கான முடிவு சிக்கலாகும், இது வெளியீட்டை உண்மையாக்குகிறது. இந்த சிக்கல் NP-முழுமையானது. மேலும், சுற்றுவட்டத்தில் உள்ள எந்த வாயிலும் ஒரு NOR வாயிலாக இருக்கும் வகையில் கட்டுப்பாடுகள் மாற்றப்பட்டால், இதன் விளைவாக ஏற்படும் சிக்கல் NP-முழுமையானதாக இருக்கும். சர்க்யூட் யு. என். எஸ். ஏ. டி சர்க்யூட் யு. என். எஸ். ஏ. டி என்பது கொடுக்கப்பட்ட பூலியன் சர்க்யூட் அதன் உள்ளீடுகளின் சாத்தியமான அனைத்து ஒதுக்கீடுகளுக்கும் தவறான வெளியீடுகளை வெளியிடுகிறதா என்பதை தீர்மானிப்பதற்கான முடிவு சிக்கலாகும். இது சர்க்யூட் SAT சிக்கலின் நிரப்பு, எனவே இணை-NP-முழுமையானது. சர்க்யூட்எஸ்ஏடி அல்லது அதன் வகைகளிலிருந்து சர்க்யூட்எஸ்ஏடி குறைப்பிலிருந்து குறைப்பு சில சிக்கல்களின் என். பி-கடினத்தன்மையைக் காட்ட பயன்படுத்தப்படலாம், மேலும் இரட்டை-ரயில் மற்றும் பைனரி லாஜிக் குறைப்புகளுக்கு மாற்றாக நமக்கு வழங்குகிறது. அத்தகைய குறைப்பு உருவாக்க வேண்டிய சாதனங்கள் பின்வருமாறுஃ ஒரு கம்பி சாதனம். இந்த சாதனம் சுற்றுவட்டத்தில் உள்ள கம்பிகளை உருவகப்படுத்துகிறது. ஒரு பிளவு சாதனம். அனைத்து வெளியீட்டு கம்பிகளும் உள்ளீட்டு கம்பியின் அதே மதிப்பைக் கொண்டுள்ளன என்பதை இந்த கேஜெட் உறுதி செய்கிறது. சுற்று வாயில்களை உருவகப்படுத்தும் கேஜெட்டுகள். ஒரு உண்மையான டெர்மினேட்டர் சாதனம். இந்த சாதனம் முழு சுற்றுவட்டத்தின் வெளியீட்டை ட்ரு என்று கட்டாயப்படுத்த பயன்படுத்தப்படுகிறது. ஒரு திருப்புமுனை சாதனம். இந்த கேஜெட் தேவைக்கேற்ப கம்பிகளை சரியான திசையில் திருப்பிவிட அனுமதிக்கிறது. ஒரு குறுக்குவெட்டு சாதனம். இந்த சாதனம் இரண்டு கம்பிகளை ஒன்றோடொன்று தொடர்பு கொள்ளாமல் கடக்க அனுமதிக்கிறது. மைன்ஸ்வீப்பர் அனுமான சிக்கல் இந்த சிக்கல் மைன்ஸ்வீப்பர் போர்டு கொடுக்கப்பட்ட அனைத்து குண்டுகளையும் கண்டுபிடிக்க முடியுமா என்று கேட்கிறது. சர்க்யூட் யு. என். எஸ். ஏ. டி சிக்கலில் இருந்து குறைப்பதன் மூலம் இது கோஎன்பி-முழுமையானது என்று நிரூபிக்கப்பட்டுள்ளது. இந்த குறைப்புக்காக கட்டப்பட்ட சாதனங்கள்ஃ கம்பி, பிளவு, மற்றும் வாயில்கள் மற்றும் முனையங்கள் அல்ல. இந்த சாதனங்கள் குறித்து மூன்று முக்கியமான அவதானிப்புகள் உள்ளன. முதலாவதாக, ஸ்ப்லிட் கேஜெட்டை நாட் கேஜெட்டாகவும், டர்ன் கேஜெட்டாகவும் பயன்படுத்தலாம். இரண்டாவதாக, அண்ட் அண்ட் நாட் கேஜெட்களை உருவாக்குவது போதுமானது, ஏனென்றால் அவை ஒன்றாக உலகளாவிய NAND கேட்டை உருவகப்படுத்த முடியும். இறுதியாக, ஒரு XOR ஐ செயல்படுத்த மூன்று NAND களை குறுக்குவெட்டு இல்லாமல் உருவாக்க முடியும் என்பதால், மேலும் ஒரு குறுக்குவெட்டை உருவாக்க XOR போதுமானது என்பதால், இது நமக்கு தேவையான குறுக்குவெட்டு சாதனத்தை வழங்குகிறது. Tseytin மாற்றம் என்பது சர்க்யூட்-SAT இலிருந்து SAT க்கு நேரடியான குறைப்பாகும். சுற்று 2-உள்ளீட்டு NAND வாயில்களிலிருந்து (பூலியன் ஆபரேட்டர்களின் செயல்பாட்டு-முழுமையான தொகுப்பு) முழுமையாக கட்டமைக்கப்பட்டிருந்தால் மாற்றத்தை விவரிப்பது எளிதுஃ சுற்றுவட்டத்தில் உள்ள ஒவ்வொரு வலையிலும் ஒரு மாறியை ஒதுக்குங்கள், பின்னர் ஒவ்வொரு NAND வாயிலுக்கும், இணை இயல்பான வடிவ உட்பிரிவுகளை உருவாக்குங்கள் (v1⁄v3) (v2⁄v3) (âv1⁄v2⁄v3), இதில் v1 மற்றும் v2 ஆகியவை NAND வாயிலுக்கான உள்ளீடுகள் மற்றும் v3 வெளியீடு. இந்த உட்பிரிவுகள் மூன்று மாறிகளுக்கு இடையிலான உறவை முழுமையாக விவரிக்கின்றன. அனைத்து வாயில்களிலிருந்தும் உட்பிரிவுகளை இணைத்து, சுற்றுவட்டத்தின் வெளியீட்டு மாறியை உண்மை என்று கட்டுப்படுத்தும் கூடுதல் உட்பிரிவுடன் இணைப்பது குறைப்பை நிறைவு செய்கிறது; அசல் சுற்று திருப்திகரமாக இருந்தால் மட்டுமே அனைத்து கட்டுப்பாடுகளையும் திருப்திப்படுத்தும் மாறிகளின் ஒரு பணி உள்ளது, மேலும் எந்தவொரு தீர்வும் சுற்று வெளியீட்டை உருவாக்கும் உள்ளீடுகளைக் கண்டுபிடிப்பதற்கான அசல் சிக்கலுக்கான தீர்வாகும். இதற்கு நேர்மாறாக-SAT என்பது சர்க்யூட்-SAT க்கு குறைக்கப்படக்கூடியது-பூலியன் சூத்திரத்தை ஒரு சுற்றாக மீண்டும் எழுதி அதைத் தீர்ப்பதன் மூலம் அற்பமாகப் பின்பற்றுகிறது. மேலும் காண்க சுற்று மதிப்பு சிக்கல் கட்டமைக்கப்பட்ட சுற்று திருப்தி திருப்தி சிக்கல் குறிப்புகள் NP-முழுமையான சிக்கல்கள் கணக்கீட்டு சிக்கல்கள் கணக்கீட்டு கோட்பாடு