Detecting Backdoor Sets with Respect to Horn and Binary Clauses.
作者： Stefan Szeider , Naomi Nishimura , Prabhakar Ragde
DOI:
关键词:
摘要: We study the parameterized complexity of detecting backdoor sets for instances propositional satisfiability problem (SAT) with respect to polynomially solvable classes horn and 2-cnf. A set is a subset variables; strong set, simplified formulas resulting from any setting these variables in class, weak there exists one which puts satisfiable formula class. show that both 2-cnf classes, detection fixed-parameter tractable (the existence size k length N can be decided time f(k)NO(1)), but W[2]-hard, implying this not tractable.
satisfiability.org 参考文章(10)
Stefan Szeider, The Parameterized Complexity of SAT Backdoors computing the australasian theory symposium. pp. 252- 261 ,(2004)
Stefan Szeider, On Fixed-Parameter Tractable Parameterizations of SAT theory and applications of satisfiability testing. pp. 188- 202 ,(2003) , 10.1007/978-3-540-24605-3_15
Bart Selman, Carla P. Gomes, Ryan Williams, Backdoors to typical case complexity international joint conference on artificial intelligence. pp. 1173- 1178 ,(2003)
William F. Dowling, Jean H. Gallier, Linear-time algorithms for testing the satisfiability of propositional horn formulae Journal of Logic Programming. ,vol. 1, pp. 267- 284 ,(1984) , 10.1016/0743-1066(84)90014-1
Karl A. Abrahamson, Rodney G. Downey, Michael R. Fellows, Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues Annals of Pure and Applied Logic. ,vol. 73, pp. 235- 276 ,(1995) , 10.1016/0168-0072(94)00034-Z
Rod G. Downey, Michael R. Fellows, Fixed-Parameter Tractability and Completeness I: Basic Results SIAM Journal on Computing. ,vol. 24, pp. 873- 921 ,(1995) , 10.1137/S0097539792228228
Bengt Aspvall, Michael F. Plass, Robert Endre Tarjan, A linear-time algorithm for testing the truth of certain quantified boolean formulas☆ Information Processing Letters. ,vol. 8, pp. 121- 123 ,(1979) , 10.1016/0020-0190(79)90002-4
Stephen A. Cook, The complexity of theorem-proving procedures symposium on the theory of computing. pp. 151- 158 ,(1971) , 10.1145/800157.805047
Marco Cesati, The turing way to parameterized complexity Journal of Computer and System Sciences. ,vol. 67, pp. 654- 685 ,(2003) , 10.1016/S0022-0000(03)00073-4
Rodney G. Downey, M. R. Fellows, Parameterized Complexity ,(1998)