Kompyuta na akili bandia · jaribio
Shinda kikomo
Mtandao, kundi la watu ambao wote wanajuana, njia ya mkato ya 1985 kupitia kuzidisha matriki, na dhana iliyodumu kwa miongo kadhaa. Maswali manne, kutoka mwanzo hadi mtaalamu, kuhusu mwisho wa Dhana ya Kliki-k.
1 · Taja kilichothibitishwa
Mwanzo
Makala inaonyesha nini kuhusu Dhana ya Kliki-k?
2 · Kokotoa gharama ya 1985
Mbinu ya Nešetřil–Poljak inapata kliki-k katika takriban hatua n^(ωk/3). Chukua k = 9 na ω = 2, thamani ya chini kabisa ambayo ω ingeweza kuwa nayo.
Kati
Mbinu ya 1985 inatoa kipeo gani cha n?
3 · Eleza “hata ikiwa ω = 2”
Dhana inatabiri gharama ya n^(ωk/3). Thamani halisi ya ω haijulikani: ni angalau 2, na makala inataja mpaka wa juu wa 9/4.
Mtaalamu
Kwa nini ni muhimu kwamba uokoaji mpya unadumu vyovyote ω itakavyokuwa, hata ω = 2?
4 · Hamisha faida
Max-2-CSP, inayojumuisha Max-Cut na Max-2-SAT, kwa vigeu n vya Boolean, ilitatuliwa katika takriban hatua 2^(ωn/3). Gawa vigeu katika makundi tisa na ugawaji wa thamani wa kila kundi unakuwa kipeo cha tatizo la kliki ya vipeo tisa yenye uzito.
Mtaalamu
Algorithimu mpya ya kliki inatoa nini kwa matatizo haya?
Kikomo kimeshindwa
—