Generating Boolean \(\mu\)-expressions (Q1892713)

We consider the class of Boolean \(\mu\)-functions, which are the Boolean functions definable by \(\mu\)-expressions (Boolean expressions in which no variable occurs more than once). We present an algorithm which transforms a Boolean formula \(E\) into an equivalent \(\mu\)-expression -- if possible -- in time linear in \(\| E \|\) times \(2^{n_ m}\), where \(\| E \|\) is the size of \(E\) and \(n_ m\) is the number of variables that occur more than once in \(E\). As an application, we obtain a polynomial time algorithm for Mundici's problem of recognizing \(\mu\)-functions from \(k\)-formulas. Furthermore, we show that recognizing Boolean \(\mu\)- functions is co-NP-complete for functions essentially dependent on all variables and we give a bound close to co-NP for the general case.