PCP theorem
கணக்கீட்டு சிக்கலான கோட்பாட்டில், பி. சி. பி தேற்றம் (பி. சி. பி குணாதிசயக் கோட்பாடு என்றும் அழைக்கப்படுகிறது), NP சிக்கலான வகுப்பில் உள்ள ஒவ்வொரு முடிவு சிக்கலும் நிலையான வினவல் சிக்கல் மற்றும் மடக்கை சீரற்ற சிக்கலின் (சீரற்ற பிட்களின் மடக்கைப் பயன்படுத்துகிறது) நிகழ்தகவு ரீதியாக சரிபார்க்கக்கூடிய ஆதாரங்களைக் (சீரற்ற வழிமுறையால் சரிபார்க்கக்கூடிய சான்றுகள்) கொண்டுள்ளது என்று கூறுகிறது. சில உலகளாவிய மாறிலி K க்கு, ஒவ்வொரு n க்கும், நீளம் n இன் அறிக்கையின் எந்தவொரு கணித ஆதாரத்தையும் நீள பாலி (n) இன் வேறுபட்ட ஆதாரமாக மீண்டும் எழுத முடியும் என்று PCP தேற்றம் கூறுகிறது, இது ஒரு சீரற்ற வழிமுறை மூலம் 99 சதவீதம் துல்லியத்துடன் முறையாக சரிபார்க்கப்படுகிறது அந்த ஆதாரத்தின் K எழுத்துக்களை மட்டுமே ஆய்வு செய்கிறது. PCP தேற்றம் தோராயத்தின் கணக்கீட்டு கடினத்தன்மை கோட்பாட்டின் மூலக்கல்லாகும், இது பல்வேறு உகப்பாக்கம் சிக்கல்களுக்கான திறமையான தோராய வழிமுறைகளை வடிவமைப்பதில் உள்ளார்ந்த சிரமத்தை ஆராய்கிறது. "குக்கின் தேற்றத்திற்குப் பிறகு சிக்கலான கோட்பாட்டின் மிக முக்கியமான முடிவு" என்று இங்கோ வெஜெனரால் விவரிக்கப்பட்டுள்ளது, மேலும் ஓடெட் கோல்ட்ரிச் "புதுமையான யோசனைகள் நிறைந்த ஈர்க்கக்கூடிய படைப்புகளின் வரிசையின் உச்சநிலை" என்று விவரித்துள்ளார். முறையான அறிக்கை PCP தேற்றம் NP = PCP [O (log n), O (1)] என்று கூறுகிறது, இதில் PCP [r (n), q (n)] என்பது ஒரு தீர்வின் நிகழ்தகவு ரீதியாக சரிபார்க்கக்கூடிய ஆதாரத்தை வழங்கக்கூடிய சிக்கல்களின் வகுப்பாகும், அதாவது ஆதாரத்தை r (n) சீரற்ற பிட்களைப் பயன்படுத்தி பல்லுறுப்புக்கோவை நேரத்தில் சரிபார்க்க முடியும் மற்றும் ஆதாரத்தின் q (n) பிட்களைப் படிப்பதன் மூலம், சரியான சான்றுகள் எப்போதும் ஏற்றுக்கொள்ளப்படுகின்றன, மேலும் தவறான சான்றுகள் குறைந்தது 1/2 நிகழ்தகவுடன் நிராகரிக்கப்படுகின்றன. n என்பது ஒரு சிக்கல் நிகழ்வின் விளக்கத்தின் பிட்களின் நீளம். சரிபார்ப்பு வழிமுறை தழுவல் அல்லாததுஃ சரிபார்க்க ஆதாரத்தின் பிட்களைத் தேர்ந்தெடுப்பது சீரற்ற பிட்கள் மற்றும் சிக்கல் நிகழ்வின் விளக்கத்தை மட்டுமே சார்ந்துள்ளது, ஆதாரத்தின் உண்மையான பிட்கள் அல்ல. பி. சி. பி மற்றும் தோராயத்தின் கடினத்தன்மை பி. சி. பி தேற்றத்தின் ஒரு மாற்று சூத்திரம், ஒரு கட்டுப்பாடு திருப்தி சிக்கலின் திருப்திகரமான கட்டுப்பாடுகளின் அதிகபட்ச பின்னம் சில நிலையான காரணிக்குள் தோராயமாக NP-கடினமானது என்று கூறுகிறது. முறைப்படி, சில மாறிலிகள் q மற்றும் α <1 க்கு, பின்வரும் உறுதிமொழி சிக்கல் (லைஸ், Lno) ஒரு NP-கடினமான முடிவெடுக்கும் சிக்கலாகும்ஃ லைஸ் = {φ: φ இல் உள்ள அனைத்து கட்டுப்பாடுகளும் ஒரே நேரத்தில் திருப்திகரமாக உள்ளன} Lno = {φ: ஒவ்வொரு வேலையும் φ இன் கட்டுப்பாடுகளில் ஒரு α பின்னத்தை விட குறைவாக திருப்திப்படுத்துகிறது, அங்கு φ என்பது ஒரு பூலியன் எழுத்தின் மீது ஒரு கட்டுப்பாடு திருப்தி சிக்கல் (CSP) ஒரு கட்டுப்பாட்டிற்கு அதிகபட்சம் q மாறிகள். ஒரு ஆதாரத்தில் நிலையான எண்ணிக்கையிலான பிட்கள் q ஐச் சரிபார்ப்பது ஆதாரத்தின் பிட்களில் q பூலியன் மாறிகளில் ஒரு தடையை மதிப்பிடுவதாகக் காணலாம் என்பதைக் கவனிப்பதன் மூலம் மேலே குறிப்பிட்ட கிளாஸ் PCP உடனான தொடர்பைக் காணலாம். சரிபார்ப்பு வழிமுறை சீரற்ற O (log n) பிட்களைப் பயன்படுத்துவதால், பாலி (n) கட்டுப்பாடுகளுடன் மேலே விவரிக்கப்பட்டுள்ளபடி அதை ஒரு CSP ஆகக் குறிப்பிடலாம். PCP தேற்றத்தின் மற்ற வகைப்பாடு பின்னர் α = 1/2 உடன் வாக்குறுதி நிபந்தனைக்கு உத்தரவாதம் அளிக்கிறதுஃ NP சிக்கலின் பதில் ஆம் என்றால், ஒவ்வொரு தடையும் (இது சீரற்ற பிட்களுக்கான ஒரு குறிப்பிட்ட மதிப்புடன் ஒத்திருக்கிறது) ஒரு திருப்திகரமான வேலையைக் கொண்டுள்ளது (ஏற்றுக்கொள்ளக்கூடிய ஆதாரம்); இல்லையெனில், எந்தவொரு ஆதாரமும் குறைந்தது 1/2 நிகழ்தகவுடன் நிராகரிக்கப்பட வேண்டும், அதாவது எந்தவொரு வேலையும் 1/2 க்கும் குறைவான தடைகளை பூர்த்தி செய்ய வேண்டும் (அதாவது இது 1/2 க்கும் குறைவான நிகழ்தகவுடன் ஏற்றுக்கொள்ளப்படும்). எனவே, வாக்குறுதி சிக்கலுக்கான ஒரு வழிமுறை அடிப்படை NP சிக்கலை தீர்க்க முடியும், எனவே வாக்குறுதி சிக்கல் NP கடினமாக இருக்க வேண்டும். இந்த தேற்றத்தின் விளைவாக, அதிகபட்ச பூலியன் சூத்திரம் திருப்தி, வரைபடங்களில் அதிகபட்ச சுயாதீன தொகுப்பு மற்றும் லாட்டிஸ்களுக்கான குறுகிய திசையன் சிக்கல் உள்ளிட்ட பல இயற்கை உகப்பாக்கம் சிக்கல்களுக்கான தீர்வுகளை P = NP தவிர திறம்பட தோராயமாக மதிப்பிட முடியாது என்பதைக் காட்டலாம். மேற்கண்ட வடிவத்தின் வாக்குறுதியளிக்கப்பட்ட சிக்கலுக்கு இதுபோன்ற பிரச்சினைகளுக்கு ஒரு தீர்வை தோராயமாக குறைப்பதன் மூலம் இதைச் செய்யலாம். இந்த முடிவுகள் சில நேரங்களில் பி. சி. பி கோட்பாடுகள் என்றும் அழைக்கப்படுகின்றன, ஏனெனில் அவை சில கூடுதல் கட்டமைப்புடன் NP க்கான நிகழ்தகவு ரீதியாக சரிபார்க்கக்கூடிய சான்றுகளாகக் கருதப்படலாம். நிரூபணம் பலவீனமான முடிவின் ஒரு சான்று, NP ஷ் PCP [n3,1] டெக்ஸ்டெர் கோசனின் சொற்பொழிவுகளில் ஒன்றில் கொடுக்கப்பட்டுள்ளது. பி. சி. பி தேற்றம் என்பது ஊடாடும் சான்றுகள் மற்றும் நிகழ்தகவு ரீதியாக சரிபார்க்கக்கூடிய சான்றுகள் குறித்த நீண்ட வரிசையின் பணியின் உச்சக்கட்டமாகும். நிலையான சான்றுகள் மற்றும் நிகழ்தகவு ரீதியாக சரிபார்க்கக்கூடிய சான்றுகள் தொடர்பான முதல் தேற்றம் NEXP ஷ் PCP [பாலி (n), பாலி (n)], மூலம் நிரூபிக்கப்பட்டுள்ளது. முதலெழுத்துக்களின் தோற்றம் குறியீடு PCPc (n), s (n) [r (n), q (n)] நிகழ்தகவு ரீதியாக சரிபார்க்கக்கூடிய ஆதாரத்தில் விளக்கப்பட்டுள்ளது. குறியீடு என்பது ஒரு குறிப்பிட்ட சிக்கலான வகுப்பைத் தரும் செயல்பாட்டின் குறியீடாகும். மேலே குறிப்பிட்டுள்ள விளக்கத்தைப் பார்க்கவும். இந்த தேற்றத்தின் பெயர் ("PCP தேற்றம்") அநேகமாக "PCP" என்பதிலிருந்து வருகிறது, அதாவது "நிகழ்தகவு ரீதியாக சரிபார்க்கக்கூடிய ஆதாரம்", அல்லது மேலே குறிப்பிட்டுள்ள குறியீட்டிலிருந்து (அல்லது இரண்டும்). முதல் தேற்றம் [1990 இல்] அதைத் தொடர்ந்து, இந்த வேலையில் பயன்படுத்தப்பட்ட முறைகள் 1991 இல் பாபாய், லான்ஸ் ஃபோர்ட்னோ, லெவின் மற்றும் செஜெடி, ஃபைஜ், கோல்ட்வாசர், லண்ட், சஃப்ரா மற்றும் செஜெடி (1991), மற்றும் அரோரா மற்றும் சஃப்ரா ஆகியோரால் 1992 இல் அரோரா, லண்ட், மோட்வானி, சூடான் மற்றும் செஜெடி ஆகியோரால் 1998 இல் பி. சி. பி தேற்றத்தின் ஆதாரத்தை வழங்க விரிவுபடுத்தப்பட்டன. 2001 கோடல் பரிசு சஞ்சீவ் அரோரா, யூரியல் ஃபைஜ், ஷாஃபி கோல்ட்வாசர், கார்ஸ்டன் லண்ட், லாஸ்லோ லோவாஸ், ராஜீவ் மோட்வானி, ஷ்முயெல் சஃப்ரா, மது சூடான் மற்றும் மரியோ ஸ்ஜெடி ஆகியோருக்கு பி. சி. பி தேற்றம் மற்றும் தோராயத்தின் கடினத்தன்மைக்கான அதன் தொடர்புக்கான பணிக்காக வழங்கப்பட்டது. 2005 ஆம் ஆண்டில் இரிட் தினூர் விரிவாக்க வரைபடங்களைப் பயன்படுத்தி பி. சி. பி தேற்றத்தின் கணிசமாக எளிமையான ஆதாரத்தைக் கண்டுபிடித்தார். இதற்காக அவர் 2019 கோடல் பரிசைப் பெற்றார். குவாண்டம் அனலாக் 2012 ஆம் ஆண்டில், தாமஸ் விடிக் மற்றும் சுயோஷி இட்டோ ஆகியோர் ஒரு முடிவை வெளியிட்டனர், இது "ஒரு மல்டிபிளேயர் விளையாட்டில் சிக்கிக் கொள்ளும் நிபுணர்களின் திறனில் வலுவான வரம்பைக் காட்டியது". இது பி. சி. பி தேற்றத்தின் குவாண்டம் அனலாக்கை நிரூபிப்பதற்கான ஒரு படியாக இருக்கலாம், ஏனெனில் இதன் முடிவு ஊடகங்களில் தெரிவிக்கப்பட்டபோது, பேராசிரியர் டோரிட் அஹரோனோவ் இதை "மல்டிப்ரூவர் ஊடாடும் சான்றுகள் குறித்த முந்தைய ஆய்வறிக்கையின் குவாண்டம் அனலாக்" என்று அழைத்தார், இது "அடிப்படையில் பி. சி. பி தேற்றத்திற்கு வழிவகுத்தது". 2018 ஆம் ஆண்டில், தாமஸ் விடிக் மற்றும் ஆனந்த் நடராஜன் ஆகியோர் சீரற்ற குறைப்பின் கீழ் குவாண்டம் பிசிபி தேற்றத்தின் ஒரு விளையாட்டு மாறுபாட்டை நிரூபித்தனர். இதில், எம்ஐபி என்பது எஃப் (என்)-பிட் கிளாசிக்கல் தகவல்தொடர்புகளைக் கொண்ட பல-நிரூபிக்கப்பட்ட குவாண்டம் ஊடாடும் சான்றுகள் அமைப்புகளின் சிக்கலான வகுப்பாகும், மேலும் முழுமை சி மற்றும் ஒலி எஸ் ஆகும். குவாண்டம் பிசிபி அனுமானத்தின் ஹாமில்டோனியன் பதிப்பு, அதாவது நிலையான வாக்குறுதி இடைவெளி சி-எஸ் கொண்ட உள்ளூர் ஹாமில்டோனியன் சிக்கல் கியூஎம்ஏ-கடினமானது, விளையாட்டின் குவாண்டம் பிசிபி தேற்றத்தைக் குறிக்கிறது. என்எல்டிஎஸ் அனுமானம் என்பது ஒரு அடிப்படை தீர்க்கப்படாத தடை மற்றும் பிசிபியின் குவாண்டம் அனலாக்கின் முன்னோடியாகும். குறிப்புகள் குறிப்புகள். . . . . . கணக்கீட்டு சிக்கலான கோட்பாட்டில் சீரற்ற வழிமுறைகள் கோட்பாடுகள்