Reversed resolution in reducing general satisfiability problem
Studia Logica 95 (3) (2010)
| Abstract | In the following we show that general property S considered by Cowen [1], Cowen and Kolany in [3] and earlier by Cowen in [2] and Kolany in [4] as hypergraph satisfiability, can be constructively reduced to (3, 2) · SAT , that is to satisfiability of (at most) triples with two-element forbidden sets. This is an analogue of the“classical” result on the reduction of SAT to 3 · SAT. | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,679 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesRobert Cowen & Katherine Wyatt (1993). BREAKUP: A Preprocessing Algorithm for Satisfiability Testing of CNF Formulas. Notre Dame Journal of Formal Logic 34 (4):602-606.
Martin Otto (2001). Two Variable First-Order Logic Over Ordered Domains. Journal of Symbolic Logic 66 (2):685-702.
V. W. Marek (2009). Introduction to Mathematics of Satisfiability. Taylor & Francis.
G. Gutiérrez, I. P. de Guzmán, J. Martínez, M. Ojeda-Aciego & A. Valverde (2002). Satisfiability Testing for Boolean Formulas Using Δ-Trees. Studia Logica 72 (1):85 - 112.
Ian Pratt-Hartmann (2008). On the Computational Complexity of the Numerically Definite Syllogistic and Related Logics. The Bulletin of Symbolic Logic 14 (1):1 - 28.
Stål O. Aanderaa, Egon Börger & Harry R. Lewis (1982). Conservative Reduction Classes of Krom Formulas. Journal of Symbolic Logic 47 (1):110-130.
Adam Kolany (1997). Consequence Operations Based on Hypergraph Satisfiability. Studia Logica 58 (2):261-272.
Adam Kolany (1993). Satisfiability on Hypergraphs. Studia Logica 52 (3):393 - 404.
Analytics
Monthly downloads |
Added to index2010-07-26Total downloads5 ( #160,368 of 549,088 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
