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.
The estimated cost of the reduction is \({\mathcal {O}(\kappa \times {\bf wd}({\mathcal E}) + \lambda \times {\bf wd}(\mathcal {F}))}\), where κ is the number of elements of \({\mathcal {E}}\) with more than thee elements, λ is the number of elements of \({\mathcal {F}}\) with more than two elements and \({{\bf wd}(\mathcal {A})}\) is the maximal cardinality of an element of \({\mathcal {A}}\). It is consistent with the classical case of κ · SAT reducibility, since then λ = 0, \({\kappa \in \mathcal {O}(\# \mathcal {E})}\), where \({\# \mathcal {E}}\) is the cardinality of \({\mathcal {E}}\) and \({{\bf wd}(\mathcal {E}) \in \mathcal {O}(k)}\), and thus we obtain \({\mathcal {O}(\kappa \times {\bf wd}(\mathcal {E}) + \lambda \times {\bf wd}(\mathcal{F})) = {\mathcal {O}}(\# \mathcal {E} \, · \, k)}\) which is the case.
Similar content being viewed by others
References
Cowen R.: ‘Property S’. Reports on Math. Logic 35, 61–74 (2001)
Cowen R.H.: ‘Hypergraph satisfiability’. Reports on Mathematical Logic 24, 113–118 (1991)
Cowen R., Kolany A.: ‘Davis-Putnam Style Rules for Deciding Property S’. Fundamenta Informaticae 79, 5–15 (2007)
Kolany A.: ‘Satisfiability on Hypergraphs’. Studia Logica 52, 393–404 (1993)
Schrijver A.: ‘The dependence of some some logical axioms on disjoint transversals and linked systems’. Colloq. Math. 39, 191–199 (1978)
West D.: Introduction to Graph Theory. Prentice-Hall, Upper Saddle River, NJ (1996)
Woodall, D.R., ‘Property B and the four-colour problem’, in D. J. Welsh and D.R. Woodall (eds.), Combinatorics, IMA, 1972.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kolany, A. Reversed Resolution in Reducing General Satisfiability Problem. Stud Logica 95, 407–416 (2010). https://doi.org/10.1007/s11225-010-9262-6
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11225-010-9262-6