رایانش و هوش مصنوعی · آزمایش
حد را بشکن
یک شبکه، گروهی از آدمها که همه یکدیگر را میشناسند، میانبری از 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-2-CSP، که Max-Cut و Max-2-SAT را در بر میگیرد، روی n متغیر بولی در حدود 2^(ωn/3) گام حل میشد. متغیرها را به نُه گروه تقسیم کن تا مقداردهی هر گروه به یک رأس از یک مسئلهٔ خوشهٔ نُهرأسیِ وزندار تبدیل شود.
پیشرفته
الگوریتم تازهٔ خوشه برای این مسئلهها چه به دست میدهد؟
حد شکسته شد
—