文章基本信息

标题：Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT
本地全文：下载
作者：Piotr Berman ; Marek Karpinski ; Alex D. Scott 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We study approximation hardness and satisfiability of bounded occurrence uniform instances of SAT. Among other things, we prove the inapproximability for SAT instances in which every clause has exactly 3 literals and each variable occurs exactly 4 times, and display an explicit approximation lower bound for this problem. We also provide a tighter characterization of the uniformly bounded occurence instances which are surely satisfiable.
关键词：Approximation Hardness , Bounded Occurrence Instances , Enforcers , Lopsided Local Lemma , lower bounds , MAX-SAT , satisfiability