Heusch, Peter
(1995).
The Complexity of the Falsifiability Problem for Pure Implicational Formulas.
Springer.
["eprint_fieldopt_monograph_type_preprint" not defined].
|
PDF
zpr95-189.pdf - Accepted Version Download (176kB) | Preview |
Abstract
Since it is unlikely that any NP-complete problem will ever be efficiently solvable, one is interested in identifying those special cases that can be solved in polynomial time. We deal with the special case of Boolean formulas where the logical implication a is the only operator and any variable (except one) occurs at most twice. For these formulas we show that an infinite hierarchy S_1subseteq S_2cdots exists such that we can test any formula from S_i for falsifiability in time O(n i ), where n is the number of variables in the formula. We describe an algorithm that finds a falsifying assignment, if one exists. Furthermore we show that the falsifiability problem for igcup_{i=1}^infty S_i is NP-complete by reducing the SAT-Problem. In contrast to the hierarchy described by Gallo and Scutella for Boolean formulas in CNF, where the test for membership in the k-th level of the hierarchy needs time O(n k ), our hierarchy permits a linear time membership test. Finally we show that S_1 is neither a sub- nor a superset of some commonly known classes of Boolean formulas, for which the SAT-Problem has linear time complexity (Horn formulas, 2-SAT, nested satisfiability).
| Item Type: | Preprints, Working Papers or Reports (["eprint_fieldopt_monograph_type_preprint" not defined]) | ||||||||
| Creators: |
|
||||||||
| URN: | urn:nbn:de:hbz:38-546951 | ||||||||
| Series Name: | Lecture notes in computer science | ||||||||
| Volume: | 969 | ||||||||
| Page Range: | pp. 221-226 | ||||||||
| Date: | 1995 | ||||||||
| Publisher: | Springer | ||||||||
| 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/54695 |
Downloads
Downloads per month over past year
Export
Actions (login required)
 |
View Item |