కంప్యూటింగ్ & ఏఐ · ప్రయోగం
పరిమితిని అధిగమించు
ఒక జాలం, అందరూ ఒకరికొకరు తెలిసిన వ్యక్తుల సమూహం, మాత్రికా గుణకారం గుండా 1985 నాటి ఒక దగ్గరి దారి, దశాబ్దాలుగా నిలిచిన ఒక పరికల్పన. k-క్లీక్ పరికల్పన ముగింపుపై, ప్రారంభ స్థాయి నుంచి నిపుణ స్థాయి వరకు, నాలుగు ప్రశ్నలు.
1 · ఏమి నిరూపించారో చెప్పు
ప్రారంభ
k-క్లీక్ పరికల్పన గురించి వ్యాసం ఏమి చూపిస్తుంది?
2 · 1985 నాటి ఖర్చును లెక్కించు
నెషెత్రిల్–పోల్యాక్ పద్ధతి ఒక 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) అడుగులలో పరిష్కరించబడేది. చరరాశులను తొమ్మిది సమూహాలుగా విభజిస్తే, ప్రతి సమూహం యొక్క విలువల కేటాయింపు ఒక భారిత తొమ్మిది-క్లీక్ సమస్యలో ఒక శీర్షం అవుతుంది.
నిపుణ
ఈ సమస్యలకు కొత్త క్లీక్ అల్గారిథమ్ ఏమి ఇస్తుంది?
పరిమితి అధిగమించబడింది
—