首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Testing satisfiability
Authors:Noga Alon  Asaf Shapira  
Institution:a Schools of Mathematics and Computer Science, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel;b School of Computer Science, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel
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 ε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, and of Czumaj and Sohler, concerning testing of graphs and hypergraphs colorability. We also discuss the difference between testing with one-sided and two-sided error.
Keywords:Property testing  Satisfiability  Hypergraph coloring
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号