கணினியியல் & செயற்கை நுண்ணறிவு · சோதனை
வரம்பை முறியடி
ஒரு வலைப்பின்னல், அனைவரும் ஒருவரையொருவர் அறிந்த ஒரு குழு, அணிப் பெருக்கல் வழியே 1985-இன் ஒரு குறுக்குவழி, பல பத்தாண்டுகள் நீடித்த ஒரு கருதுகோள். k-கிளிக் கருதுகோளின் முடிவு பற்றி, தொடக்கம் முதல் நிபுணர் வரை, நான்கு கேள்விகள்.
1 · நிரூபிக்கப்பட்டதைக் கூறு
தொடக்கம்
k-கிளிக் கருதுகோள் பற்றிக் கட்டுரை எதைக் காட்டுகிறது?
2 · 1985-இன் செலவைக் கணக்கிடு
Nešetřil–Poljak முறை ஒரு k-கிளிக்கைச் சுமார் n^(ωk/3) படிகளில் கண்டறிகிறது. k = 9, ω = 2 என எடுத்துக்கொள்; ω கொண்டிருக்கக்கூடிய மிகக் குறைந்த மதிப்பு அது.
இடைநிலை
1985-இன் முறை n-இன் எந்த அடுக்குக்குறியைத் தருகிறது?
3 · “ω = 2 ஆனாலும்” என்பதை விளக்கு
கருதுகோள் n^(ωk/3) என்ற செலவை முன்கணிக்கிறது. ω-வின் துல்லியமான மதிப்பு தெரியாது: அது குறைந்தது 2; கட்டுரை 9/4 என்ற மேல் வரம்பைக் குறிப்பிடுகிறது.
நிபுணர்
புதிய சேமிப்பு ω எதுவாக இருந்தாலும், ω = 2 ஆனாலும், நீடிப்பது ஏன் முக்கியம்?
4 · ஆதாயத்தைக் கொண்டுசெல்
Max-Cut, Max-2-SAT ஆகியவற்றை உள்ளடக்கிய Max-2-CSP, n பூலியன் மாறிகளின் மீது, சுமார் 2^(ωn/3) படிகளில் தீர்க்கப்பட்டு வந்தது. மாறிகளை ஒன்பது குழுக்களாகப் பிரி; ஒவ்வொரு குழுவின் மதிப்பிருத்தலும் எடையிட்ட ஒன்பது-கிளிக் சிக்கலின் ஓர் உச்சியாகிறது.
நிபுணர்
புதிய கிளிக் வழிமுறை இந்தச் சிக்கல்களுக்கு எதைத் தருகிறது?
வரம்பு முறியடிக்கப்பட்டது
—