MIN-FORMULA $\in$ NP
I am thinking about the following problem: Show that MIN-FORMULA $\in$ NP.
MIN-FORMULA is the set of minimal boolean formulas, i.e. formulas such that there is no shorter formula that computes the same boolean function.
I would like to have an advise whether or not the following approach/idea is ok.
Show by describing a non-deterministic algorithm N that solves the question of elementhood in polytime:
On a given formula $\phi$:
Construct non-deterministically (i.e. simultaneously) all boolean formulas $\psi$ such that
- $\psi$ is smaller than $\phi$ and
- $\psi$ contains all variables of $\phi$.
Check all resulting formulas $\psi$ for equivalence with $\phi$. If none is equivalent, ACCEPT, otherwise, REJECT.
Thank you.
Solution 1:
The solution proposed seems wrong. Recall that when building a turing machine that uses non-determinism, if any path accepts,
So we cannot ACCEPT if none is equivalent: we can only take ACCEPT decisions from one of the branches of computation, not all of them!
A solution set to the above problem uses that this problem is $\overline{\texttt{NP}}$ : That is, the complement of $\texttt{NP}$, where we can ACCEPT from all branches, and REJECT from one branch.