Matrisskärningarna av Lovász och Schrijver är metoder för att strama åt linjära avslappningar av noll-ett-program genom tillägg av nya linjära ojämlikheter. Vi tar upp frågan om hur många nya ojämlikheter som krävs för att tillnärma vissa kombinatoriska problem med starka garantier, och för att lösa vissa fall av Boolesk tillfredsställelse. Vi visar att avkopplingar av linjära program, som erhållits genom åtdragning via någon subexponentiell storlek semidefinit Lovász-Schrijver härledning träd, inte kan ungefärlig max-k-SAT till en faktor bättre än 1 +, max-k-XOR till en faktor bättre än 2 − ε, eller vertex täcka till en faktor bättre än 7/6. Vi visar exponentiella storlek lägre gränser för träd-liknande Lovász-Schrijver bevis på otillfredsställande för flera framträdande otillfredsställande CNF, inklusive slumpmässiga 3-CNF formler, slumpmässiga system av linjära ekvationer, och Tseitin graf formler. Dessutom bevisar vi att trädliknande LS + inte polynomiskt simulerar trädliknande skärplan, och att trädliknande LS + inte polynomiskt simulerar obegränsad upplösning. Alla våra nedre gränser för härledning träd är baserade på kopplingar mellan storleken och höjden på härledning träd (dess rank). Den primära metoden är en trädstorlek/rank-avsättning för Lovász-Schrijver vederläggningar: Liten trädstorlek innebär liten rankning. Förvånansvärt nog håller detta inte för att härleda godtyckliga linjära ojämlikheter. Vi visar att för LS 0 och LS finns det exempel med polynom-storlek träd-liknande derivat, men kräver linjär rank.
En ny artikel om Pitassi och Segerlind REF visar exponentiellt lägre gränser för trädliknande LS+-bevis för otillfredsställande för flera viktiga klasser av CNF, och visar också att trädliknande LS+-bevis inte effektivt kan simulera vissa andra standardsäkra system.
Exponential lower bounds and Integrality Gaps for Tree-like Lovász-Schrijver Procedures
{'venue': 'Electronic Colloquium on Computational Complexity', 'journal': 'Electronic Colloquium on Computational Complexity (ECCC)', 'mag_field_of_study': ['Mathematics', 'Computer Science']}