کمپیوٹنگ اور مصنوعی ذہانت · تجربہ
حد کو مات دو
ایک نیٹ ورک، لوگوں کا ایک گروہ جس میں سب ایک دوسرے کو جانتے ہیں، میٹرکسوں کی ضرب کے ذریعے 1985 کا ایک مختصر راستہ، اور ایک مفروضہ جو دہائیوں تک قائم رہا۔ چار سوال، ابتدائی سے ماہر تک، k-کلیک مفروضے کے خاتمے کے بارے میں۔
1 · بتاؤ کہ کیا ثابت ہوا
ابتدائی
مضمون k-کلیک مفروضے کے بارے میں کیا دکھاتا ہے؟
2 · 1985 کی لاگت کا حساب لگاؤ
Nešetřil–Poljak طریقہ تقریباً n^(ωk/3) قدموں میں ایک k-کلیک ڈھونڈتا ہے۔ 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) قدموں میں حل ہوتا تھا۔ متغیرات کو نو گروہوں میں بانٹو تو ہر گروہ کی قدروں کی تفویض ایک وزنی نو-کلیک مسئلے کا ایک راس بن جاتی ہے۔
ماہر
نیا کلیک الگورتھم ان مسائل کے لیے کیا دیتا ہے؟
حد کو مات ہو گئی
—