Reversed Resolution in Reducing General Satisfiability Problem

Studia Logica 95 (3):407-416 (2010)
  Copy   BIBTEX

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.

Categories

Keywords

Reprint years

DOI

10.1007/s11225-010-9262-6

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,846

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Satisfiability on hypergraphs.Adam Kolany - 1993 - Studia Logica 52 (3):393-404.
Hypergraph Satisfiability.R. Cowen - 1991 - Reports on Mathematical Logic.
Pool resolution is NP-hard to recognize.Samuel R. Buss - 2009 - Archive for Mathematical Logic 48 (8):793-798.
Property S.Robert Cowen - 2001 - Reports on Mathematical Logic:61-74.
Combinatorial Analytic Tableaux.Robert Cowen - 1993 - Reports on Mathematical Logic:29-39.
On the computational complexity of the numerically definite syllogistic and related logics.Ian Pratt-Hartmann - 2008 - Bulletin of Symbolic Logic 14 (1):1-28.
Conservative reduction classes of Krom formulas.Stål O. Aanderaa, Egon Börger & Harry R. Lewis - 1982 - Journal of Symbolic Logic 47 (1):110-130.
The guarded fragment with transitive guards.Wiesław Szwast & Lidia Tendera - 2004 - Annals of Pure and Applied Logic 128 (1-3):227-276.
The decision problem for restricted universal quantification in set theory and the axiom of foundation.Franco Parlamento & Alberto Policriti - 1992 - Mathematical Logic Quarterly 38 (1):143-156.
Products, or how to create modal logics of high complexity.M. Marx & S. Mikulás - 2001 - Logic Journal of the IGPL 9 (1):71-82.
On α-satisfiability and its α-lock resolution in a finite lattice-valued propositional logic.Xingxing He, Jun Liu, Yang Xu, Luis Martínez & Da Ruan - 2012 - Logic Journal of the IGPL 20 (3):579-588.
The Complexity of Resolution Refinements.Joshua Buresh-Oppenheim & Toniann Pitassi - 2007 - Journal of Symbolic Logic 72 (4):1336 - 1352.
Lewis Dichotomies in Many-Valued Logics.Simone Bova - 2012 - Studia Logica 100 (6):1271-1290.
Checking Validity of Quantifier-Free Formulas in Combinations of First-Order Theories.Clark Wayne Barrett - 2003 - Dissertation, Stanford University
On the Relations Between Discrete and Continuous Complexity Theory.Klaus Meer - 1995 - Mathematical Logic Quarterly 41 (2):281-286.

Analytics

Added to PP
2010-07-26

Downloads
66 (#245,871)

6 months
11 (#237,138)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Satisfiability on hypergraphs.Adam Kolany - 1993 - Studia Logica 52 (3):393-404.
Hypergraph Satisfiability.R. Cowen - 1991 - Reports on Mathematical Logic.
Property S.Robert Cowen - 2001 - Reports on Mathematical Logic:61-74.

Add more references