Abstrakt. De bästa aktuella uppskattningarna av tröskelvärdena för förekomsten av lösningar i slumpmässiga problem med begränsad tillfredsställelse (CSPs) härrör främst från den första och andra momentmetoden. Men bortsett från några få undantagsfall ger dessa metoder inte riktigt motsvarande övre och nedre gränser. Enligt djupa men icke-rigorösa argument från statistisk mekanik beror denna diskrepans på en förändring i geometrin hos den uppsättning lösningar som kallas kondensation och som inträffar strax före den faktiska tröskeln för lösningarnas existens (Krzakala, Montanari, Ricci-Tersenghi, Semerjian, Zdeborová: PNAS 2007). För att klara av kondensering har fysiker utvecklat en sofistikerad men icke-rigorös formalism som kallas Survey Propagation (Mézard, Parisi, Zecchina: Science 2002). Denna formalism ger exakta gissningar om tröskelvärdena för många slumpmässiga CSP. Här utvecklar vi en ny Survey Propagation inspirerad andra stund metod för random k-NAESAT problem, som är ett av standardriktmärke problem i teorin om slumpmässiga CSPs. Denna nya teknik gör det möjligt för oss att övervinna den barriär som kondensen utgör rigoröst. Vi bevisar att tröskeln för förekomsten av lösningar i slumpmässig k-NAESAT är 2 k-1 ln 2 − ( ln 2 2 ) + ε k, där  och k ≤ 2 −(1-o k (1))k, vilket verifierar den statistiska mekaniken för detta problem.
I REF fick vi ett resultat som liknade Theorem 1 för det (symmetriska) slumpmässiga k-NAESAT-problemet.
Catching the k-NAESAT Threshold
{'venue': 'Proc. 44th STOC (2012) 899 - 908)', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}