ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR03-022 | 11th April 2003 00:00

Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT

RSS-Feed

Abstract:

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.



ISSN 1433-8092 | Imprint