Show that if $P = NP$, then deciding whether a boolean formula is minimal is in $P$. Recall a boolean formula $\phi$ over $n$ variables is minimal if there does not exist a shorter formula $\phi'$ over the same set of variables so that $\phi(\bar a) = \phi'(\bar a)$ for every $\bar a \in \{0,1\}^n$.
This question really stumps me because given a boolean formula $\phi$ of length $k$, just enumerating the set of formulas of length $k-1$ requires something obscene as noted by Dedekind:
http://en.wikipedia.org/wiki/Dedekind_number
And suppose I have this $\phi'$, just verifying $\phi' \equiv \phi$ requires checking all $2^n$ possible assignments, which is already more than polynomial.
One way forward is to reduce minimizing $\phi$ to some other problem that would be polytime solvable if P=NP, but I cannot think of such a problem. 
 A: Given two Boolean formulae $\phi$ and $\phi'$, the problem of determining whether there is some $\bar a$ such that $\phi(\bar a)\ne \phi'(\bar a)$ is in $NP$, since you can nondeterministically guess such an $\bar a$ and then verify in polynomial time that it satisfies $\phi(\bar a)\ne \phi'(\bar a)$.  So, assuming $P=NP$, there's a polynomial-time algorithm for checking whether $\phi\equiv\phi'$.  Then determining whether there is a shorter $\phi'$ than $\phi$ such that $\phi\equiv\phi'$ is in $NP$, since you can nondeterministically guess a $\phi'$ and then check in polynomial time whether it is equivalent to $\phi$.  So, deciding whether or not a Boolean formula is minimal is in $NP$, and under the assumption $P=NP$ it's then also in $P$.
Addendum: Given an algorithm for an $NP$-complete problem, I will explain how to construct an explicit polynomial-time algorithm for this problem.  To explain it simply, I will suppose that the $NP$-complete problem is SAT, the problem of determining whether a set of Boolean clauses is satisfiable.


*

*Write a nondeterministic program $P$ which takes as input formulae $\phi$ and $\phi'$ and nondeterministically chooses an arbitrary input $\bar a$ for $\phi$ and $\phi'$, and then accepts if $\phi({\bar a})\ne \phi'({\bar a})$ and rejects otherwise.  Since Boolean formulae can be evaluated in polynomial time, $P$ will run in polynomial time.

*$P$ will have an accepting computation if and only if there is some $\bar a$ such that $\phi({\bar a})\ne \phi'({\bar a})$, i.e., iff $\phi\not\equiv \phi'$.  Otherwise, all possible computations of $P$ will be rejecting.

*Write a set of clauses $C$ that simulate the nondeterministic computation that $P$ performs on its input, so that the clauses are satisfiable if and only if $P$ has an accepting computation.  For a given set of clauses $C$, sequence of variables $\bar w$, and sequence of Boolean values $\bar b$, I will write $C(\bar w:=\bar b)$ for the set of clauses resulting from setting the variables $\bar w$ equal to the values $\bar b$ in $C$.  Then, if $\bar v$ is the sequence of variables used in $C$ to encode which formula $\phi$ is input to $P$, $\bar v'$ is the sequence of variables used in $C$ to encode which formula $\phi'$ is input, and $\bar F$ is a map from formulae to sequences of Boolean values that describes the way in which the input to $P$ is coded, then $C(\bar v:=\bar F(\phi))(\bar v':=\bar F(\phi'))$ will be satisfiable if and only if $P$ has an accepting computation on $\phi$ and $\phi'$, i.e., iff $\phi\not\equiv \phi'$.

*Write another nondeterministic polynomial-time program $Q$ which, given an input formula $\phi$, nondeterministically chooses an arbitrary formula $\phi'$ shorter than $\phi$, and then, using the polynomial-time algorithm for SAT which is supposed to exist, determines whether $C':=C(\bar v:=\bar F(\phi))(\bar v':=\bar F(\phi'))$ is satisfiable.  $Q$ will then accept if $C'$ was not satisfiable and reject otherwise.

*$Q$ will have an accepting computation iff there is some formula $\phi'$ shorter than $\phi$ such that $\phi\equiv\phi'$.  Otherwise, all computations of $Q$ will be rejecting.

*Write a set of clauses $D$ which simulates the computation of $Q$, and let $\bar y$ be the variables in $D$ used to encode which formula $\phi$ is input to $Q$.  Supposing that the input to $Q$ is coded in the same way that the input to $P$ was, $D(\bar y:=\bar F(\phi))$ will then be satisfiable if and only if $Q$ has an accepting computation on $\phi$, i.e., iff $\phi$ is not minimal.

*Now use the polynomial-time algorithm for SAT to determine whether or not the set of clauses $D(\bar y:=\bar F(\phi))$ is satisfiable.  If it is satisfiable, $\phi$ is not minimal; if it is not satisfiable, $\phi$ is minimal.
