# The Complexity of the Falsifiability Problem for Pure Implicational Formulas

Heusch, Peter
(1999)
*The Complexity of the Falsifiability Problem for Pure Implicational Formulas.*
**Published in: **
Discrete Applied Mathematics Vol. 96-97.
pp. 127-138.

## Abstract

We consider Boolean formulas where logical implication (->) is the only operator and all variables, except at most one (denoted z), occur at most twice. We show that the problem of determining falsifiability for formulas of this class is NP-complete but if the number of occurrences of z is restricted to be at most k then there is an O(|F|) algorithm for certifying falsifiability. We show this hierarchy of formulas, indexed on k, is interesting because even lower levels (e.g., k=2) are not subsumed by several well-known polynomial time solvable classes of formulas.

ZAIK Number: | zpr95-189a |
---|---|

Depositing User: | Archive Admin |

Date Deposited: | 02 Apr 2001 00:00 |

Last Modified: | 31 Oct 2011 16:14 |

URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/189001 |