TY - GEN

T1 - Testing satisfiability

AU - Alon, Noga

AU - Shapira, Asaf

PY - 2002/1/1

Y1 - 2002/1/1

N2 - Let Φ be a set of general boolean functions on n variables, such that each function depends on exactly k variables, and each variable can take a value from [l,d]-We say that Φ is ϵ-far from satisfiable, if one must remove at least ϵnk functions in order to make the set of remaining functions satisfiable. Our main result is that if Φ is ϵ-far from satisfiable, then most of the induced sets of functions, on sets of variables of size c(k,d)/ϵ2, are not satisfiable, where c(k,d) depends only on k and d. Using the above claim, we obtain similar results for k-SAT and k-NAEQ-SAT. Assume we relax the decision problem of whether an instance of one of the above mentioned problems is satisfiable or not, to the problem of deciding whether an instance is satisfiable or ϵ-far from satisfiable. While the above decision problems are NP-hard, our result implies that we can solve their relaxed versions, that is, distinguishing between satisfiable and ϵ-far from satisfiable instances, in randomized constant time. From the above result we obtain as a special case, previous results of Alon and Krivelevich [3] and of Czumaj and Sohler [8], concerning testing of graphs and hypergraphs colorability. We also discuss the problem of testing whether a graph G can be d-colored, such that it does not contain any copy of a colored graph from a fixed, given set of colored graphs.

AB - Let Φ be a set of general boolean functions on n variables, such that each function depends on exactly k variables, and each variable can take a value from [l,d]-We say that Φ is ϵ-far from satisfiable, if one must remove at least ϵnk functions in order to make the set of remaining functions satisfiable. Our main result is that if Φ is ϵ-far from satisfiable, then most of the induced sets of functions, on sets of variables of size c(k,d)/ϵ2, are not satisfiable, where c(k,d) depends only on k and d. Using the above claim, we obtain similar results for k-SAT and k-NAEQ-SAT. Assume we relax the decision problem of whether an instance of one of the above mentioned problems is satisfiable or not, to the problem of deciding whether an instance is satisfiable or ϵ-far from satisfiable. While the above decision problems are NP-hard, our result implies that we can solve their relaxed versions, that is, distinguishing between satisfiable and ϵ-far from satisfiable instances, in randomized constant time. From the above result we obtain as a special case, previous results of Alon and Krivelevich [3] and of Czumaj and Sohler [8], concerning testing of graphs and hypergraphs colorability. We also discuss the problem of testing whether a graph G can be d-colored, such that it does not contain any copy of a colored graph from a fixed, given set of colored graphs.

UR - http://www.scopus.com/inward/record.url?scp=0012575225&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0012575225&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0012575225

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 645

EP - 654

BT - Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

PB - Association for Computing Machinery

T2 - 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

Y2 - 6 January 2002 through 8 January 2002

ER -