Tech Reports

ULCS-09-011

On Constructing Minimal Formulae

Paul E. Dunne


Abstract

Given a Boolean propositional formula, F(X_n) over the basis {And,Or, eg} we consider the following decision problem: is there a subset of literals, S, for which F(Xn)equiv (And_{yin S} y) or F(Xn)equiv (Or_{yin S} y)? We prove that the “obvious” Sigma_{2}^{p} upper bound is sub-optimal and that the problem is decidable in P^{NP}_{||} the class of languages decidable by polynomial time methods allowed to make non-adaptive queries to an NP oracle. We further show that the associated function problem of computing a witnessing such subset when one exists can be solved in FP^{NP}_{||}.

[Full Paper]