Låt P vara en k-ary predikat över en ändlig alfabetet. Betrakta en slumpmässig CSP(P ) instans I över n variabler med m begränsningar. När m n instansen kommer att vara otillfredsställande med hög sannolikhet och vi vill hitta ett certifikat om otillfredsställande. När P är den 3-åriga OR predicate, är detta det välstuderade problemet med att vederlägga slumpmässiga 3-SAT formler och en effektiv algoritm är känd endast när m n 3/2. Att förstå den densitet som krävs för att vederlägga andra predikat är viktigt i kryptografi, beviskomplexitet och inlärningsteori. Tidigare var det känt att för en k-ary predikat, med m n k/2 begränsningar räcker för vederläggning. Vi ger ett kriterium för predikat som ofta ger effektiva motbevisningsalgoritmer vid mycket lägre densiteter. Specifikt, om P misslyckas med att stödja en t-wise enhetlig fördelning, då finns det en effektiv algoritm som vederlägger slumpmässiga CSP(P) fall whp när m n t/2. I själva verket kommer vår algoritm "något starkt" vederlägga instansen I, att certifiera Opt(I) ≤ 1 −  på k (1). Om t = k får vi starkaste möjliga motbevisning, certifiering Opt(I) ≤ E[P ] + o(1). Det sista resultatet är nytt även för slumpmässig k-SAT. Tidigare arbete på SDP hierarkier har gett vissa bevis för att effektiv vederläggning av slumpmässig CSP(P ) kan vara omöjligt när m n t/2 ; således finns det en indikation på att vår algoritms beroende av m är optimalt för varje P, åtminstone i samband med SDP hierarkier. Som en tillämpning av vårt resultat, vi förfalskar antaganden som används för att visa hårdhet-of-learning i nyligen arbete av Daniely, Linial, och Shalev-Shwartz. Problem med begränsad tillfredsställelse spelar en viktig roll inom datavetenskapen. Det finns en stor teori [23] om hur algebraiska egenskaper hos en CSP-predikat påverkar dess värsta fall satisfiability komplexitet; det finns en liknande omfattande teori [68] om värsta fall tillnärmning av CSPs. Slutligen finns det ett rikt utbud av forskning - från områdena datavetenskap, matematik och fysik - om den genomsnittliga komplexiteten i slumpmässiga CSPs; se [2] för en undersökning bara av slumpmässiga k-SAT. Detta dokument handlar om slumpmässiga CSPs, och i synnerhet problemet med att effektivt vederlägga tillfredsställande för slumpmässiga fall. Detta är en välstuderad algoritmisk uppgift med kopplingar till t.ex. bevis komplexitet [20] Historiskt är slumpmässiga CSPs förmodligen bäst studeras i fallet k-SAT, k ≥ 3. Modellen här innebär att välja en CNF formel I över n variabler genom att rita m klausuler (ORs of k bokstavliga) oberoende och enhetligt slumpmässigt. Detta är ett av de mest kända effektiva sätten att generera svåra fall av NP-fullständiga och coNP-fullständiga problem. Beräkningshårdheten beror avgörande på densiteten, α = m/n. För varje k finns det (troligen) en konstant kritisk densitet α k sådan att jag är tillfredsställande med hög sannolikhet när α < α k, och jag är otillfredsställande med hög sannolikhet när α > α k. (Här och hela, "med hög sannolikhet (whp)" betyder med sannolikhet 1 − o(1) som n → ∞.) Detta fenomen inträffar för alla icke-triviala slumpmässiga CSP:er; när det gäller k-SAT har det noggrant bevisats [35] för tillräckligt stor k. Det finns en naturlig algoritmisk uppgift i samband med var och en av de två regimerna. När α < α k man vill hitta en tillfredsställande uppgift för mig. När α > α k man vill vederlägga I; d.v.s. hitta ett intyg om otillfredsställande. De flesta heuristiska SAT-solvare använder DPLL-baserade algoritmer; i otillfredsställande fall producerar de certifikat som kan ses som motbevis inom resolutionssäkra systemet. Mer allmänt är en vederläggningsalgoritm för densitet α någon algoritm som: a) utgångar "otillfredsställande" eller "misslyckas", b) aldrig felaktigt utgångar "otillfredsställande", c) utgångar "misslyckas" med låg sannolikhet (dvs. sannolikhet o(1)). 1 Empiriskt arbete tyder på att när α ökar mot α k, att hitta tillfredsställande uppdrag blir svårare; och omvänt, när α ökar bortom α k, att hitta certifikat om otillfredsställande gradvis blir lättare. Ett seminalpapper av Chvátal och Szemerédi [25] visade att för alla tillräckligt stora heltal c (beroende på k), en slumpmässig k-SAT instans med m = cn kräver upplösning vederläggningar av storlek 2 (n) (whp). Å andra sidan visade Fu [46] att polynom-storlek upplösning vederläggningar finns (whp) en gång m ≥ O(n k−1 ); Beame et al. [18] 1 Vi varnar läsaren för att vi i detta papper inte betraktar det besläktade, men distinkta, scenariot att särskilja planterade slumpmässiga fall från verkligt slumpmässiga.
Vi brie y undersökning det tidigare arbetet med att vederlägga slumpmässiga CSPs-vi hänvisar läsaren till REF för en grundlig undersökning om ämnet.
How to Refute a Random CSP
{'venue': '2015 IEEE 56th Annual Symposium on Foundations of Computer Science', 'journal': '2015 IEEE 56th Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}