المرجع يسأل: مرحلة الانتقال في السبت

Question

هذا ليس سؤالا فني، آمل أن يكون لدى هذا المجتمع مجالا لهذه الأسئلة، لكنني سأحذفه في حالة عدم ملاءمة هذا.

قد لوحظ تجريبيا (مثل هنا ) عند اختيار $ 3 $ formula من العملية التالية:

على المدخلات $ (n، \ alpha n) $ : اختر $ \ alpha n $ clauses بشكل موحد عشوائيا من مجموعة جميع بنود جميع البنود $ 3 $ حرفي فوق $ x_1، \ Ldots، x_n $

الاحتمال أن الصيغة المخرجة راضية تعتمد على $ \ ألفا $ : إذا كان $ \ alpha \ ll c $ الاحتمال قريب جدا من $ 1 $ ، وإذا كان $ \ alpha \ gg c $ الاحتمال قريب جدا من $ 0 $ (وقد لوحظ لعامة $ K $ مثيلات -Sat ).

سؤالي هو ما هو الفهم النظري لهذه المشكلة؟ إلى حد علمي، لمشاكل أخرى، من الممكن إثبات مطالبات مماثلة بسهولة (مثل الاحتمال أن الرسم البياني عشوائي $ g (n، p) $ لديه زمرة من الحجم $ 4 $ هو تقريبا $ 1 $ عندما $ p (n)=omega (n ^ {- 2/3}) $ ويقبل $ 0 $ عند $ p (n)= o (n ^ {- 2/3}) $ ، ويمكن إثباتها من خلال الاستخدام الأساسي للحظات الثانية).

ومع ذلك، ل SAT I & # 8217؛ ر العثور على البراهين. هل تعرف أي تقدم في هذه المشكلة؟

Answer 1

النتائج الأكثر صحة ذات صلة هي:

1. ehud friedgut، عتبات حادة من خصائص الرسم البياني، و $ k $ مشكلة -sat . توضح هذه الورقة (مع ملحق من قبل Jean Bourgain) أن $ K $ -Sat يعرض عتبة حادة. ومع ذلك، قد تعتمد هذه العتبة السابقة على $ n $ (أي، لا يمكن أن تظهر هذه الطريقة أن $ \ alpha $ ثابت).
2. Jian ding، Allan Sly، Nike Sun، دليل على تخمين الرضا عن $ K $ . يحدد المؤلفون القيمة الدقيقة ل $ \ alpha $ for $ k \ geq k_0 $ . تم حساب هذه القيمة من $ \ ألفا $ $ من قبل الفيزيائيون الذين يستخدمون طريقة التجويف، ولكن حججهم ليست صارمة.

العمل ذات الصلة يناقش هندسة مساحة الحل من $ k $ -Sat حول عتبات مختلفة. انظر على سبيل المثال Dimitris Achlioptas، Amin Coja-Oghlan، Federico Ricci-Tersenghi، على هندسة فضاء الحل لمشاكل الرضا القيد العشوائي .