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}_{||}.

For each technical report listed here, copyright and all intellectual property rights remain with the respective authors. Copyright is effective from the year of publication in each case. By downloading a file from this page, you agree to use it only for purposes of research and scholarship. Any other use of this material or storage of it in any medium or its sale or distribution in any form is expressly forbidden without prior written permission from the authors concerned.