Testing satisfiability

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 satisfiable, if one must remove at least εn^k 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)ε², 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.

REFERENCES

• 1: N. Alon, Testing Subgraphs in Large Graphs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.434, October 14-17, 2001
• 2: N. Alon , R. A. Duke , H. Lefmann , V. Rödl , R. Yuster, The algorithmic aspects of the regularity lemma, Journal of Algorithms, v.16 n.1, p.80-109, Jan. 1994 [doi>10.1006/jagm.1994.1005]
• 3: Noga Alon , Michael Krivelevich, Testing k-colorability, SIAM Journal on Discrete Mathematics, v.15 n.2, p.211-227, 2002 [doi>10.1137/S0895480199358655]
• 4: N. Alon and J. H. Spencer, The probabilistic method, Second Edition, Wiley, New York, 2000.
• 5: G. Andersson and L. Engebretsen, Property Testers For Dense Non-Boolean Constraint Satisfaction Programs, in preparation.
• 6: B. Bollobás, P. Erdös, M. Simonovits and E. Szemerédi, Extremal graphs without large forbidden subgraphs, Annals of Discrete Mathematics 3 (1978), 29-41.
• 7: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 8: Artur Czumaj , Christian Sohler, Testing Hypergraph Coloring, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.493-505, July 08-12, 2001
• 9: A. Frieze and R. Kannan, Quick approximation to matrices and applications, Combinatorica, 19, (1999), 175-220.
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 11: Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
• 12: Johan Håstad, Some optimal inapproximability results, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.1-10, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258536]
• 13: Howard Karloff , Uri Zwick, A 7/8-Approximation Algorithm for MAX 3SAT?, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.406, October 19-22, 1997
• 14: V. Rödl and R. Duke, On graphs with small subgraphs of large chromatic number, Graphs and Combinatorics 1 (1985), 91-96.
• 15: D. Ron, Property Testing. To appear in P. M. Pardalos, S. Rajasekaran, J. Reif, and J. D. P. Rolim, editors, Handbook of Randomized Algorithms. Kluwer Academic Publishers, 2001.
• 16: E. Szemerédi, Regular partitions of graphs, In: Proc. Colloque Inter. CNRS (J. C. Bermond, J. C. Fournier, M. Las Vergnas and D. Sotteau, eds.), 1978, 399-401.