| Testing Satisability (2007) | |||||||||||||||
Abstract | |||||||||||||||
| 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 [1; d]. We say that is -far from satisable, if one must remove at least n k functions in order to make the set of remaining functions satisable. Our main result is that if is -far from satisable, then most of the induced sets of functions, on sets of variables of size c(k; d)= 2, are not satisable, 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 satis able or not, to the problem of deciding whether an instance is satisable or -far from satisable. While the above decision problems are NP-hard, our result implies that we can solve their relaxed versions, that is, distinguishing between satisable and -far from satisable 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 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||