संगणन आणि एआय · प्रयोग
मर्यादेवर मात कर
एक जाळे, एकमेकांना ओळखणाऱ्या लोकांचा एक गट, आव्यूहांच्या गुणाकारातून जाणारा 1985 चा एक लघुमार्ग, आणि दशकानुदशके टिकलेली एक परिकल्पना. k-क्लीक परिकल्पनेच्या अंतावर चार प्रश्न, नवशिक्यापासून तज्ज्ञापर्यंत.
1 · काय सिद्ध झाले ते सांग
नवशिक्या
k-क्लीक परिकल्पनेबद्दल लेख काय दाखवतो?
2 · 1985 चा खर्च काढ
नेशेत्रिल–पोल्याक पद्धत सुमारे n^(ωk/3) पायऱ्यांत k-क्लीक शोधते. k = 9 आणि ω = 2 घे, ω चे शक्य असलेले सर्वात कमी मूल्य.
मध्यम
1985 ची पद्धत n चा कोणता घातांक देते?
3 · “ω = 2 असले तरीही” स्पष्ट कर
परिकल्पना n^(ωk/3) इतक्या खर्चाचे भाकीत करते. ω चे नेमके मूल्य अज्ञात आहे: ते किमान 2 आहे, आणि लेख 9/4 ही वरची मर्यादा उद्धृत करतो.
तज्ज्ञ
नवी बचत ω काहीही असो, अगदी ω = 2 असले तरी टिकते, हे का महत्त्वाचे आहे?
4 · फायदा पुढे ने
n बूलियन चलांवरील Max-2-CSP, ज्यात Max-Cut आणि Max-2-SAT येतात, सुमारे 2^(ωn/3) पायऱ्यांत सोडवला जात असे. चलांची नऊ गटांत विभागणी कर, आणि प्रत्येक गटाला दिलेली मूल्ये भारित नऊ-क्लीक समस्येचा एक शिरोबिंदू बनतात.
तज्ज्ञ
नवा क्लीक-अल्गोरिदम या समस्यांसाठी काय देतो?
मर्यादेवर मात
—