Unique games conjecture
கணக்கீட்டு சிக்கலான கோட்பாட்டில், தனித்துவமான விளையாட்டு அனுமானம் (பெரும்பாலும் யுஜிசி என்று குறிப்பிடப்படுகிறது) 2002 ஆம் ஆண்டில் சுபாஷ் கோட் உருவாக்கிய ஒரு அனுமானமாகும். ஒரு தனித்துவமான விளையாட்டு என்று அழைக்கப்படும் ஒரு குறிப்பிட்ட வகை விளையாட்டின் தோராயமான மதிப்பை தீர்மானிப்பதில் உள்ள சிக்கல் NP-கடினமான கணக்கீட்டு சிக்கலைக் கொண்டுள்ளது என்று அனுமானம் கூறுகிறது. தோராயத்தின் கடினத்தன்மை கோட்பாட்டில் இது பரந்த பயன்பாடுகளைக் கொண்டுள்ளது. தனித்துவமான விளையாட்டு அனுமானம் உண்மை மற்றும் P ஷ்ணூ NP என்றால், பல முக்கியமான சிக்கல்களுக்கு பல்லுறுப்புக்கோவை நேரத்தில் ஒரு சரியான தீர்வை பெறுவது சாத்தியமற்றது மட்டுமல்லாமல், ஒரு நல்ல பல்லுறுப்புக்கோவை-நேர தோராயத்தைப் பெறுவதும் சாத்தியமற்றது. இத்தகைய பொருத்தமற்ற விளைவு ஏற்படுத்தும் சிக்கல்களில் கட்டுப்பாடு திருப்தி சிக்கல்கள் அடங்கும், அவை பல்வேறு வகையான துறைகளில் உருவாகின்றன. இது உண்மையா இல்லையா என்பதில் கல்வி உலகம் சமமாக பிளவுபட்டுள்ளதாகத் தோன்றுவதால் இந்த அனுமானம் அசாதாரணமானது. சூத்திரங்கள் தனித்துவமான விளையாட்டு அனுமானத்தை பல சமமான வழிகளில் கூறலாம். தனித்துவமான லேபிள் கவர் தனித்துவமான விளையாட்டு அனுமானத்தின் பின்வரும் உருவாக்கம் பெரும்பாலும் தோராயத்தின் கடினத்தன்மையில் பயன்படுத்தப்படுகிறது. தனித்துவமான கட்டுப்பாடுகளுடன் லேபிள் கவர் என்று அழைக்கப்படும் பின்வரும் வாக்குறுதி சிக்கலின் NP-கடினத்தன்மையை இந்த அனுமானம் முன்வைக்கிறது. ஒவ்வொரு விளிம்பிற்கும், இரண்டு செங்குத்துகளில் உள்ள வண்ணங்கள் சில குறிப்பிட்ட வரிசைப்படுத்தப்பட்ட ஜோடிகளுக்கு மட்டுப்படுத்தப்பட்டுள்ளன. தனித்துவமான கட்டுப்பாடுகள் என்பது ஒவ்வொரு விளிம்பிற்கும் வரிசைப்படுத்தப்பட்ட ஜோடிகள் எதுவும் ஒரே முனைக்கு ஒரே நிறத்தைக் கொண்டிருக்கவில்லை என்பதாகும். இதன் பொருள் என்னவென்றால், அளவு k இன் எழுத்துக்களில் தனித்துவமான கட்டுப்பாடுகளைக் கொண்ட லேபிள் அட்டையின் ஒரு நிகழ்வை πe: [k] → [k] வரிசைமாற்றங்களின் தொகுப்புடன் ஒரு இயக்கிய வரைபடமாக குறிப்பிடலாம், இது வரைபடத்தின் ஒவ்வொரு விளிம்பிற்கும் ஒன்று. ஒரு லேபிள் கவர் நிகழ்வுக்கான ஒரு பணி G இன் ஒவ்வொரு உச்சிக்கும் [k] = {1,2,. k} தொகுப்பில் ஒரு மதிப்பைக் கொடுக்கிறது, இது பெரும்பாலும் "வண்ணங்கள்" என்று அழைக்கப்படுகிறது. அத்தகைய நிகழ்வுகள் ஒரு உச்சியின் நிறம் அதன் அண்டை நாடுகளின் வண்ணங்களை தனித்துவமாக வரையறுக்கிறது என்ற பொருளில் வலுவாக கட்டுப்படுத்தப்படுகின்றன, எனவே அதன் முழு இணைக்கப்பட்ட கூறுகளுக்கும். எனவே, உள்ளீட்டு நிகழ்வு ஒரு செல்லுபடியாகும் வேலையை ஏற்றுக்கொண்டால், அத்தகைய வேலையை ஒரு முனையின் அனைத்து வண்ணங்களிலும் மீண்டும் செய்வதன் மூலம் திறமையாகக் காணலாம். குறிப்பாக, கொடுக்கப்பட்ட நிகழ்வு ஒரு திருப்திகரமான வேலையை ஏற்றுக்கொள்கிறதா என்பதை தீர்மானிக்கும் சிக்கலை பல்லுறுப்புக்கோவை நேரத்தில் தீர்க்க முடியும். ஒரு தனித்துவமான லேபிள் கவர் நிகழ்வின் மதிப்பு என்பது எந்தவொரு வேலையாலும் திருப்திப்படுத்தக்கூடிய கட்டுப்பாடுகளின் பகுதியாகும். திருப்திகரமான நிகழ்வுகளுக்கு, இந்த மதிப்பு 1 மற்றும் கண்டுபிடிக்க எளிதானது. மறுபுறம், திருப்தியற்ற விளையாட்டின் மதிப்பை தீர்மானிப்பது மிகவும் கடினமாகத் தெரிகிறது, தோராயமாக கூட. தனித்துவமான விளையாட்டு அனுமானம் இந்த சிரமத்தை முறைப்படுத்துகிறது. மேலும் முறைப்படி, தனித்துவமான கட்டுப்பாடுகளுடன் (சி, எஸ்)-இடைவெளி லேபிள்-கவர் சிக்கல் பின்வரும் வாக்குறுதி சிக்கலாகும் (லைஸ், எல்னோ): லைஸ் = {ஜிஃ சில பணி குறைந்தபட்சம் ஜி இல் உள்ள கட்டுப்பாடுகளின் சி-பகுதியையாவது திருப்திப்படுத்துகிறது} எல்னோ = {ஜிஃ ஒவ்வொரு பணியும் ஜி இல் உள்ள கட்டுப்பாடுகளின் அதிகபட்ச எஸ்-பகுதியை திருப்திப்படுத்துகிறது, அங்கு ஜி என்பது தனித்துவமான கட்டுப்பாடுகளுடன் லேபிள் கவர் சிக்கலின் ஒரு எடுத்துக்காட்டு. தனித்துவமான விளையாட்டு அனுமானம், ஒவ்வொரு போதுமான சிறிய ஜோடி மாறிலிகளுக்கு ε, δ> 0, ஒரு நிலையான k உள்ளது என்று கூறுகிறது, அதாவது (1 − δ, ε)-இடைவெளி லேபிள்-கவர் சிக்கல் அளவு k இன் எழுத்துக்களில் தனித்துவமான கட்டுப்பாடுகளுடன் NP-கடினமானது. வரைபடங்களுக்கு பதிலாக, லேபிள் கவர் சிக்கலை நேரியல் சமன்பாடுகளின் அடிப்படையில் வடிவமைக்க முடியும். எடுத்துக்காட்டாக, முழு எண்களின் மாடுலோ 7 க்கு மேல் நேரியல் சமன்பாடுகளின் அமைப்பு நம்மிடம் உள்ளது என்று வைத்துக்கொள்வோம்ஃ இது தனித்துவமான கட்டுப்பாடுகளுடன் லேபிள் கவர் சிக்கலின் ஒரு எடுத்துக்காட்டு. எடுத்துக்காட்டாக, முதல் சமன்பாடு வரிசைமாற்றத்துடன் (1,2) ஒத்திருக்கிறது, அங்கு (1,2) (x1) = 2x2 மாடுலோ 7. இரண்டு-ஆதார ஆதார அமைப்புகள் ஒரு தனித்துவமான விளையாட்டு என்பது இரண்டு-ஆதார ஒரு சுற்று (2P1R) விளையாட்டின் ஒரு சிறப்பு வழக்கு ஆகும். இரண்டு நிரூபிக்கப்பட்ட ஒரு சுற்று விளையாட்டில் இரண்டு வீரர்கள் (புரோவர்ஸ் என்றும் அழைக்கப்படுகிறார்கள்) மற்றும் ஒரு நடுவர் உள்ளனர். நடுவர் ஒவ்வொரு வீரருக்கும் அறியப்பட்ட நிகழ்தகவு விநியோகத்திலிருந்து ஒரு கேள்வியை அனுப்புகிறார், மேலும் வீரர்கள் ஒவ்வொருவரும் ஒரு பதிலை அனுப்ப வேண்டும். பதில்கள் நிலையான அளவின் தொகுப்பிலிருந்து வருகின்றன. வீரர்களுக்கு அனுப்பப்படும் கேள்விகள் மற்றும் அவர்கள் வழங்கிய பதில்களைப் பொறுத்து ஒரு முன்கணிப்பு மூலம் விளையாட்டு குறிப்பிடப்படுகிறது. விளையாட்டின் போது ஒருவருக்கொருவர் தொடர்பு கொள்ள முடியாவிட்டாலும், வீரர்கள் ஒரு மூலோபாயத்தை முன்கூட்டியே தீர்மானிக்கலாம். முன்கணிப்பு அவர்களின் கேள்விகள் மற்றும் அவர்களின் பதில்களால் திருப்தி அடைந்தால் வீரர்கள் வெற்றி பெறுகிறார்கள். முதல் வீரரின் ஒவ்வொரு கேள்விக்கும் ஒவ்வொரு பதிலுக்கும், இரண்டாவது வீரரின் சரியான ஒரு பதில் இருந்தால், வீரர்களுக்கு வெற்றி கிடைக்கும், மற்றும் நேர்மாறாகவும் இருந்தால் இரண்டு-ஆதாரம் கொண்ட ஒரு சுற்று விளையாட்டு ஒரு தனித்துவமான விளையாட்டு என்று அழைக்கப்படுகிறது. ஒரு விளையாட்டின் மதிப்பு என்பது அனைத்து உத்திகளிலும் வீரர்களின் அதிகபட்ச வெற்றி நிகழ்தகவு ஆகும். தனித்துவமான விளையாட்டு அனுமானம், போதுமான அளவு சிறிய ஜோடி மாறிலிகள் ε, δ> 0 க்கு, பின்வரும் வாக்குறுதி சிக்கல் (லைஸ், எல்னோ) NP-கடினமாக இருக்கும் வகையில் ஒரு நிலையான k உள்ளது என்று கூறுகிறதுஃ லைஸ் = {G: G இன் மதிப்பு குறைந்தது 1 − δ} Lno = {G: G இன் மதிப்பு அதிகபட்சமாக ε} ஆகும், அங்கு G என்பது ஒரு தனித்துவமான விளையாட்டு, அதன் பதில்கள் k அளவு தொகுப்பிலிருந்து வருகின்றன. சாத்தியமான சரிபார்க்கக்கூடிய சான்றுகள் மாற்றாக, தனித்துவமான விளையாட்டு அனுமானம் NP இல் உள்ள சிக்கல்களுக்கு ஒரு குறிப்பிட்ட வகை நிகழ்தகவு சரிபார்க்கக்கூடிய ஆதாரத்தின் இருப்பை முன்வைக்கிறது. ஒரு தனித்துவமான விளையாட்டை வினவல் சிக்கலான 2 உடன் ஒரு சிறப்பு வகையான தகவமைப்பு அல்லாத நிகழ்தகவு ரீதியாக சரிபார்க்கக்கூடிய ஆதாரமாக பார்க்க முடியும், அங்கு சரிபார்ப்பவரின் ஒவ்வொரு ஜோடி சாத்தியமான கேள்விகளுக்கும் முதல் வினவலுக்கான ஒவ்வொரு சாத்தியமான பதிலுக்கும், சரிபார்ப்பவரை ஏற்றுக்கொள்ள வைக்கும் இரண்டாவது வினவலுக்கு சரியாக ஒரு சாத்தியமான பதில் உள்ளது, மற்றும் நேர்மாறாகவும். தனித்துவமான விளையாட்டு அனுமானம், ஒவ்வொரு போதுமான சிறிய ஜோடி மாறிலிகளுக்கும் ஒரு மாறிலி உள்ளது என்று கூறுகிறது, அதாவது NP இல் உள்ள ஒவ்வொரு சிக்கலும் முழுமை, ஒலி மற்றும் சீரற்ற சிக்கலான அளவு கொண்ட ஒரு எழுத்துக்களின் மீது நிகழ்தகவு ரீதியாக சரிபார்க்கக்கூடிய ஆதாரத்தைக் கொண்டுள்ளது, இது ஒரு தனித்துவமான விளையாட்டு. தோராயத்தின் கடினத்தன்மை கோட்பாட்டில் சில கேள்விகளில் முன்னேற்றம் காண்பதற்காக 2002 ஆம் ஆண்டில் சுபாஷ் கோட் தனித்துவமான விளையாட்டு அனுமானத்தை அறிமுகப்படுத்தினார். தனித்துவமான விளையாட்டு அனுமானத்தின் உண்மை பல அறியப்பட்ட தோராயமான வழிமுறைகளின் உகந்த தன்மையைக் குறிக்கும் (P § NP என்று வைத்துக் கொள்ளுங்கள்). எடுத்துக்காட்டாக, கோமேன்ஸ் மற்றும் வில்லியம்சனின் வழிமுறை மூலம் ஒரு வரைபடத்தில் அதிகபட்ச வெட்டு தோராயமாக அடையப்பட்ட தோராய விகிதம், தனித்துவமான விளையாட்டு அனுமானம் மற்றும் P § NP ஐக் கருதி எந்த சேர்க்கை மாறிலிக்கும் உகந்ததாக இருக்கும். தனித்துவமான விளையாட்டு அனுமானம் குறிக்கும் முடிவுகளின் பட்டியல் அருகிலுள்ள அட்டவணையில் பலவீனமான அனுமானம் P § NP க்கான தொடர்புடைய சிறந்த முடிவுகளுடன் காட்டப்பட்டுள்ளது. ஒவ்வொரு மாறிலிக்கும் (சிக்கல் அளவைப் பொறுத்தவரை) முடிவு முறையே அதிகமாகவோ அல்லது குறைவாகவோ இருக்கும் என்று ஒரு மாறிலி அல்லது பொருள். கலந்துரையாடல் மற்றும் மாற்று வழிகள் தற்போது, தனித்துவமான விளையாட்டு அனுமானத்தின் உண்மை குறித்து ஒருமித்த கருத்து இல்லை. ஊகத்தின் சில வலுவான வடிவங்கள் நிராகரிக்கப்பட்டுள்ளன. ஒரு தனித்துவமான விளையாட்டின் மதிப்பு குறைந்தபட்சம் மதிப்பு அதிகபட்சமாக இருக்கும் சந்தர்ப்பத்திலிருந்து வேறுபடும் போது வழக்கை வேறுபடுத்துவது பல்லுறுப்புக்கோவை-நேர வழிமுறைகளுக்கு சாத்தியமற்றது (ஆனால் ஒருவேளை NP-கடினமாக இல்லை) என்று அனுமானத்தின் வேறு வடிவம் முன்வைக்கிறது. அனுமானத்தின் இந்த வடிவம் தோராயத்தின் கடினத்தன்மையில் உள்ள பயன்பாடுகளுக்கு இன்னும் பயனுள்ளதாக இருக்கும். P = NP இல்லையென்றால், அனுமானத்தின் மேற்கண்ட சூத்திரங்களில் உள்ள மாறிலி அவசியம். தனித்துவத் தேவை நீக்கப்பட்டால், அதனுடன் தொடர்புடைய அறிக்கை இணையான மறு செய்கை தேற்றத்தால் உண்மை என்று அறியப்படுகிறது, மாரேக் கார்பின்ஸ்கி மற்றும் வாரன் ஷூடி கூட தனித்துவமான விளையாட்டு சிக்கலின் அடர்த்தியான நிகழ்வுகளுக்கான நேரியல் நேர தோராயத் திட்டங்களை உருவாக்கியுள்ளனர். 2008 ஆம் ஆண்டில், பிரசாத் ராகவேந்திரா தனித்துவமான விளையாட்டு அனுமானம் உண்மையாக இருந்தால், ஒவ்வொரு கட்டுப்பாடு திருப்தி சிக்கலுக்கும் சிறந்த தோராய விகிதம் ஒரு குறிப்பிட்ட எளிய அரை வரையறுக்கப்பட்ட நிரலாக்க நிகழ்வால் வழங்கப்படுகிறது, இது குறிப்பாக பல்லுறுப்புக்கோவையில் உள்ளது. 2010 ஆம் ஆண்டில், பிரசாத் ராகவேந்திரா மற்றும் டேவிட் ஸ்டீயூரர் ஆகியோர் கேப்-ஸ்மால்-செட் விரிவாக்க சிக்கலை வரையறுத்து, அது NP-கடினமானது என்று யூகித்தனர். இந்த அனுமானம் தனித்துவமான விளையாட்டு அனுமானத்தை குறிக்கிறது. முழுமையான இருதரப்பு துணை வரைபடங்களைக் கண்டுபிடிப்பதற்கான தோராயமான முடிவுகளின் வலுவான கடினத்தன்மையை நிரூபிக்கவும் இது பயன்படுத்தப்படுகிறது. 2010 ஆம் ஆண்டில், சஞ்சீவ் அரோரா, போவாஸ் பராக் மற்றும் டேவிட் ஸ்டீயூரர் ஆகியோர் தனித்துவமான விளையாட்டு சிக்கலுக்கான ஒரு சப்எக்ஸ்போனென்ஷியல் நேர தோராய வழிமுறையைக் கண்டறிந்தனர். 2012 ஆம் ஆண்டில், குறைந்தபட்சம் மதிப்புள்ள நிகழ்வுகளிலிருந்து அதிகபட்ச மதிப்புள்ள நிகழ்வுகளை வேறுபடுத்துவது NP-கடினமானது என்று காட்டப்பட்டது. 2018 ஆம் ஆண்டில், தொடர்ச்சியான ஆவணங்களுக்குப் பிறகு, 2-2 விளையாட்டு அனுமானம் என்று அழைக்கப்படும் அனுமானத்தின் பலவீனமான பதிப்பு நிரூபிக்கப்பட்டது. ஒரு குறிப்பிட்ட அர்த்தத்தில், இது அசல் அனுமானத்தின் "பாதி" என்பதை நிரூபிக்கிறது. இது தனித்துவமான லேபிள் கவர்க்கான சிறந்த அறியப்பட்ட இடைவெளியை மேம்படுத்துகிறதுஃ குறைந்தபட்சம் மதிப்புள்ள நிகழ்வுகளிலிருந்து அதிகபட்ச மதிப்புள்ள நிகழ்வுகளை வேறுபடுத்துவது NP-கடினம். குறிப்புகள் குறிப்புகள். 2002 கணிப்பு தோராய வழிமுறைகளில் கணிப்பு சிக்கலான கோட்பாடு கணிப்பு கடினத்தன்மை அனுமானங்கள் கணினி அறிவியலில் தீர்க்கப்படாத சிக்கல்கள் அனுமானங்கள்