Abstract-Den hardcore modellen är en modell av lattice gassystem som har fått mycket uppmärksamhet inom statistisk fysik, sannolikhetsteori och teoretisk datavetenskap. Det är sannolikhetsfördelningen över oberoende uppsättningar I av en graf som viktas proportionellt mot λ  på I med fugacity parameter λ. Vi bevisar att vid den unika tröskeln för den hardcore modellen på d-regelbunden träd, approximering partition funktion blir beräknings svårt på grafer av maximal grad d. Speciellt visar vi att om NP=RP det inte finns något polynom tid approximationsschema för partition funktion (summan av sådana viktade oberoende uppsättningar) på grafer av maximal grad d för fugacity är unikhet tröskel på d-regelbunden träd och ε(d) > 0 är en positiv konstant. Weitz [36] producerade en FPTAS för approximering av partitionsfunktionen när 0 < λ < λc(d) så detta resultat visar att beräkningströskeln exakt sammanfaller med den statistiska fysikfasövergången vilket bekräftar huvudantagandet av [30]. Vi analyserar vidare specialfallet av λ = 1, d = 6 och visar att det inte finns något polynom tid approximationsschema för ungefär räkna oberoende uppsättningar på grafer av maximal grad d = 6, vilket är optimalt, förbättra den tidigare gränsen av d = 24. Vårt bevis är baserat på speciellt konstruerade slumpmässiga bipartit grafer som fungerar som prylar i en minskning till MAX-CUT. Genom att bygga vidare på den andra momentet metodanalys av [30] och i kombination med en analys av rekonstruktionsproblem på trädet vårt bevis etablerar en stark version av "replica" metod heuristik som utvecklats av teoretiska fysiker. Resultatet etablerar den första rigorösa korrespondensen mellan hårdheten av ungefärlig räkning och provtagning med statistiska fysikfasövergångar.
Sannolikheten bevisades av Sly i REF för den hardcore modellen.
Computational Transition at the Uniqueness Threshold
{'venue': '2010 IEEE 51st Annual Symposium on Foundations of Computer Science', 'journal': '2010 IEEE 51st Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Computer Science', 'Mathematics', 'Physics']}