We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Reversed Resolution in Reducing General Satisfiability Problem.
- Authors
Kolany, Adam
- 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.
- Subjects
SECRETARY problem (Probability theory); PROPOSITIONAL calculus; HYPERGRAPHS; NUMBER theory; SET theory; ESTIMATION theory
- Publication
Studia Logica, 2010, Vol 95, Issue 3, p407
- ISSN
0039-3215
- Publication type
Article
- DOI
10.1007/s11225-010-9262-6