Informatik & KI · das Experiment
Unterbiete die Grenze
Ein Netzwerk, eine Gruppe von Personen, die sich alle gegenseitig kennen, eine Abkürzung von 1985 über die Matrizenmultiplikation und eine Hypothese, die jahrzehntelang hielt. Vier Fragen, vom Einsteiger bis zum Experten, zum Ende der k-Clique-Hypothese.
1 · Sag, was bewiesen wurde
Einsteiger
Was zeigt der Artikel über die k-Clique-Hypothese?
2 · Berechne den Aufwand von 1985
Die Methode von Nešetřil–Poljak findet eine k-Clique in etwa n^(ωk/3) Schritten. Nimm k = 9 und ω = 2, den kleinsten Wert, den ω haben könnte.
Fortgeschritten
Welchen Exponenten von n ergibt die Methode von 1985?
3 · Erkläre das „sogar wenn ω = 2“
Die Hypothese sagt einen Aufwand von n^(ωk/3) voraus. Der genaue Wert von ω ist unbekannt: Er ist mindestens 2, und der Artikel nennt eine obere Schranke von 9/4.
Experte
Warum ist es wichtig, dass die neue Ersparnis für jeden Wert von ω gilt, sogar für ω = 2?
4 · Übertrage den Gewinn
Max-2-CSP, das Max-Cut und Max-2-SAT umfasst, wurde für n boolesche Variablen in etwa 2^(ωn/3) Schritten gelöst. Teile die Variablen in neun Gruppen auf, und jede Belegung einer Gruppe wird zu einem Knoten eines gewichteten Neun-Cliquen-Problems.
Experte
Was liefert der neue Cliquen-Algorithmus für diese Probleme?
Grenze unterboten
—