期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We prove approximation hardness of short symmetric instances of MAX-3SAT in which each literal occurs exactly twice, and each clause is exactly of size 3. We display also an explicit approximation lower bound for that problem. The bound two on the number of occurrences of literals in symmetric MAX-3SAT is thus the smallest possible one which makes the instances hard to approximate
关键词：Approximation Hardness , Balanced Enforcers , Gap Property , Linear Equations. , MAX-3SAT , NP-completeness , Symmetric Instances
