Reversed Resolution in Reducing General Satisfiability Problem

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.