Porschen, Stefan and Speckenmeyer, Ewald
(2007).
Clause Set Structures and Polynomial-Time SAT-Decidable Classes.
Working Paper.
|
PDF
zaik2007-537.pdf Download (168kB) | Preview |
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.
| Item Type: | Preprints, Working Papers or Reports (Working Paper) | ||||||||||||
| Creators: |
|
||||||||||||
| URN: | urn:nbn:de:hbz:38-549095 | ||||||||||||
| Date: | 2007 | ||||||||||||
| Language: | English | ||||||||||||
| Faculty: | Faculty of Mathematics and Natural Sciences | ||||||||||||
| Divisions: | Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science | ||||||||||||
| Subjects: | Data processing Computer science | ||||||||||||
| Refereed: | No | ||||||||||||
| URI: | http://kups.ub.uni-koeln.de/id/eprint/54909 |
Downloads
Downloads per month over past year
Export
Actions (login required)
 |
View Item |