Clause Set Structures and Polynomial-Time SAT-Decidable Classes

Porschen, Stefan and Speckenmeyer, Ewald (2007) Clause Set Structures and Polynomial-Time SAT-Decidable Classes.
Technical Report , 12 p.

Abstract

Proposing a fibre view on propositional clause sets, we investigate satisfiability testing for several CNF subclasses. Specifically, we show how to decide SAT in polynomial time for formulas where each pair of different clauses intersect either in all or in one variable.


Actions:
Download: [img] Postscript
Download (344kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2007-537
Depositing User: Stefan Porschen
Date Deposited: 19 Apr 2007 00:00
Last Modified: 19 Dec 2011 09:45
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/537