On Constructing Minimal Formulae
Paul E.S. Dunne · The Computer Journal · 2010
Given a Boolean propositional formula, φ(Xn) over the basis Ω = {∧, V, ¬}, we consider the following decision problem: is there a subset of literals, S, for which φ(Xn) ≡ ∧y∈Sy or φ(Xn) ≡ ⋁y∈Sy? We prove that the ‘obvious’ Σ2p upper bound is suboptimal 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.