Valiant–Vazirani theorem
வாலியன்ட்-வஜீரானி தேற்றம் என்பது கணக்கீட்டு சிக்கல் கோட்பாட்டில் ஒரு தேற்றமாகும், இது தெளிவான-SAT க்கு ஒரு பல்லுறுப்புக்கோவை நேர வழிமுறை இருந்தால், NP = RP என்று கூறுகிறது. 1986 இல் வெளியிடப்பட்ட தனித்துவமான தீர்வுகளைக் கண்டறிவது போல் NP எளிதானது என்ற தலைப்பில் லெஸ்லி வாலியன்ட் மற்றும் விஜய் வஜிராணி ஆகியோர் தங்கள் கட்டுரையில் நிரூபித்தனர். இந்த ஆதாரம் முல்முலி-வஜிரானி-வஜிரானி தனிமைப்படுத்தப்பட்ட லெம்மாவை அடிப்படையாகக் கொண்டது, இது பின்னர் கோட்பாட்டு கணினி அறிவியலில் பல முக்கியமான பயன்பாடுகளுக்கு பயன்படுத்தப்பட்டது. Valiant-Vazirani தேற்றம் பூலியன் திருப்திகரமான சிக்கல், இது NP-முழுமையானது, உள்ளீட்டு நிகழ்வுகள் அதிகபட்சம் ஒரு திருப்திகரமான வேலையைக் கொண்டிருப்பதாக உறுதியளிக்கப்பட்டாலும் கூட கணக்கீட்டு ரீதியாக கடினமான சிக்கலாகவே உள்ளது என்பதைக் குறிக்கிறது. தெளிவான அவுட்லைன் சந்தேகத்திற்கு இடமின்றி-SAT என்பது கொடுக்கப்பட்ட பூலியன் சூத்திரம் அதிகபட்சமாக ஒரு திருப்திகரமான வேலையைக் கொண்டிருக்கிறதா அல்லது சரியாக ஒரு திருப்திகரமான வேலையைக் கொண்டிருக்கிறதா என்பதைத் தீர்மானிப்பதற்கான வாக்குறுதித் சிக்கலாகும். முதல் வழக்கில், தெளிவின்மை-SAT க்கான ஒரு வழிமுறை நிராகரிக்கப்பட வேண்டும், இரண்டாவதாக அது சூத்திரத்தை ஏற்றுக்கொள்ள வேண்டும். சூத்திரம் ஒன்றுக்கு மேற்பட்ட திருப்திகரமான வேலையைக் கொண்டிருந்தால், வழிமுறையின் நடத்தைக்கு எந்த நிபந்தனையும் இல்லை. வாக்குறுதியின் சிக்கலான தெளிவான-SAT ஐ ஒரு நிர்ணயிக்கப்படாத டூரிங் இயந்திரத்தால் தீர்மானிக்க முடியும், இது அதிகபட்சமாக ஒரு ஏற்றுக்கொள்ளும் கணக்கீட்டு பாதையைக் கொண்டுள்ளது. இந்த அர்த்தத்தில், இந்த வாக்குறுதி சிக்கல் சிக்கலான வகுப்பு யுபி (இது பொதுவாக மொழிகளுக்கு மட்டுமே வரையறுக்கப்படுகிறது) க்கு சொந்தமானது. வாலியன்ட்-வஜீரானி தேற்றத்தின் ஆதாரம் SAT இலிருந்து SAT க்கு ஒரு நிகழ்தகவு குறைப்பைக் கொண்டுள்ளது, அதாவது நிகழ்தகவுடன் குறைந்தபட்சம், வெளியீட்டு சூத்திரம் அதிகபட்சமாக ஒரு திருப்திகரமான வேலையைக் கொண்டுள்ளது, இதனால் சந்தேகத்திற்கு இடமில்லாத-SAT சிக்கலின் வாக்குறுதியை திருப்திப்படுத்துகிறது. இன்னும் துல்லியமாக, குறைப்பு என்பது ஒரு சீரற்ற பல்லுறுப்புக்கோவை-நேர வழிமுறையாகும், இது ஒரு பூலியன் சூத்திரத்திற்கு மாறிகளுடன் ஒரு பூலியன் சூத்திரத்தை வரைபடமாக்குகிறது, அதாவது ஒவ்வொரு திருப்திகரமான வேலையும் திருப்தி அளிக்கிறது, மேலும் திருப்திகரமாக இருந்தால், குறைந்தபட்சம் நிகழ்தகவுடன், ஒரு தனித்துவமான திருப்திகரமான வேலையைக் கொண்டுள்ளது. குறைப்பை பல்லுறுப்புக்கோவை எண்ணிக்கையில் இயக்குவதன் மூலம், ஒவ்வொரு முறையும் புதிய சுயாதீனமான சீரற்ற பிட்களுடன், நாம் சூத்திரங்களைப் பெறுகிறோம். தேர்ந்தெடுக்கும்போது, குறைந்தபட்சம் ஒரு சூத்திரம் தனித்துவமாக திருப்திகரமாக இருக்கும் நிகழ்தகவு திருப்திகரமாக இருந்தால் குறைந்தபட்சம் என்று நாம் பெறுகிறோம். இது SAT இலிருந்து சந்தேகத்திற்கு இடமில்லாத-SAT க்கு ஒரு டூரிங் குறைப்பை வழங்குகிறது, ஏனெனில் சந்தேகத்திற்கு இடமில்லாத-SAT க்கான ஒரு கருதப்பட்ட வழிமுறை பயன்படுத்தப்படலாம். பின்னர் SAT இன் சுய-குறைப்பு ஒரு திருப்திகரமான வேலையை கணக்கிட பயன்படுத்தப்படலாம், அது இருந்தால். ஒட்டுமொத்தமாக, இது NP = RP ஐ RP இல் தீர்க்க முடியும் என்பதை நிரூபிக்கிறது. குறைப்பின் யோசனை சூத்திரத்தின் தீர்வு இடத்தை சீரற்ற அஃபைன் ஹைப்பர்பிளேன்களுடன் வெட்டுவதாகும், அங்கு சீரற்ற முறையில் ஒரே மாதிரியாக தேர்ந்தெடுக்கப்படுகிறது. ஒரு மாற்று ஆதாரம் முல்முலி, வஜீரானி மற்றும் வஜீரானி ஆகியோரின் தனிமைப்படுத்தப்பட்ட லெம்மாவை அடிப்படையாகக் கொண்டது. அவர்கள் மிகவும் பொதுவான அமைப்பைக் கருத்தில் கொள்கிறார்கள், மேலும் இங்குள்ள அமைப்பிற்கு இது பயன்படுத்தப்படுகிறது, இது தனிமைப்படுத்தப்பட்ட நிகழ்தகவை மட்டுமே வழங்குகிறது. குறிப்புகள் கட்டமைப்பு சிக்கல் கோட்பாடு கணக்கீட்டு சிக்கல் கோட்பாட்டில் தேற்றம்