Polynomial Time SAT Decision, Hypergraph Transversals and the Hermitian Rank
作者： Nicola Galesi , Oliver Kullmann
DOI: 10.1007/11527695_8
关键词: Bounded function 、 Graph theory 、 Boolean satisfiability problem 、 Mathematics 、 Hypergraph 、 Discrete mathematics 、 Rank (linear algebra) 、 Time complexity 、 Linear algebra 、 Hermitian matrix 、 Combinatorics
摘要: Combining graph theory and linear algebra, we study SAT problems of low “linear algebra complexity”, considering formulas with bounded hermitian rank. We show polynomial time decision the class rank at most one, applying methods from hypergraph transversal theory. Applications to heuristics for algorithms structure minimally unsatisfiable clause-sets are discussed.
springer.com
springerlink.com
swan.ac.uk 
swansea.ac.uk 参考文章(14)
Oliver Kullmann, Investigating a general hierarchy of polynomially decidable classes of CNF's based on short tree-like resolution proofs Electronic Colloquium on Computational Complexity. ,(1999)
Oliver Kullmann, The Combinatorics of Conflicts between Clauses theory and applications of satisfiability testing. pp. 426- 440 ,(2003) , 10.1007/978-3-540-24605-3_32
Claude Berge, Hypergraphs: Combinatorics of Finite Sets ,(2011)
Michael Doob, Aleksandar Torgašev, Dragoš M. Cvetković, Ivan Gutman, Recent Results in the Theory of Graph Spectra ,(1988)
Thomas Eiter, Georg Gottlob, Identifying the Minimal Transversals of a Hypergraph and Related Problems SIAM Journal on Computing. ,vol. 24, pp. 1278- 1304 ,(1995) , 10.1137/S0097539793250299
O. Kullmann, On a generalization of extended resolution Discrete Applied Mathematics. ,vol. 96, pp. 149- 176 ,(1999) , 10.1016/S0166-218X(99)00037-2
James R. Bunch, Linda Kaufman, Some stable methods for calculating inertia and solving symmetric linear systems Mathematics of Computation. ,vol. 31, pp. 163- 179 ,(1977) , 10.1090/S0025-5718-1977-0428694-0
Hans Kleine Büning, Xishun Zhao, On the structure of some classes of minimal unsatisfiable formulas Discrete Applied Mathematics. ,vol. 130, pp. 185- 207 ,(2003) , 10.1016/S0166-218X(02)00405-5
Thomas Eiter, Exact Transversal Hypergraphs and Application to Boolean µ-Functions Journal of Symbolic Computation. ,vol. 17, pp. 215- 225 ,(1994) , 10.1006/JSCO.1994.1013
Oliver Kullmann, Upper and Lower Bounds on the Complexity of Generalised Resolution and Generalised Constraint Satisfaction Problems Annals of Mathematics and Artificial Intelligence. ,vol. 40, pp. 303- 352 ,(2004) , 10.1023/B:AMAI.0000012871.08577.0B