User:Tizio/Minimization of Boolean formulae
 | This is not a Wikipedia article: This is a workpage, a collection of material and work in progress that may or may not be incorporated into an article. It should not necessarily be considered factual or authoritative. |
In computer science, the minimization of Boolean formulae is the problem of finding a Boolean formula of minimal size that is equivalent to another given Boolean formula or represents another given Boolean function. A manual method for solving this problem is that of Karnaugh maps; automated algorithms include the Quine–McCluskey algorithm and is variant Petrick's method.
The decision problem corresponding to minimization is that of establishing whether a formula is of mimimal size. This problem is harder than NP-hard problems (...in some cases...); this was the original motivation behind the introduction of the polynomial hierarchy. The exact complexity of this problem in its general form is currently unknown, but complete characterizations for some subcases have been established.
To do
- Example: two equivalent formulae of different size
- Various notions of minimality
- Complexity known (NP-complete) for the Horn case
- Hemaspaandra, E. and Wechsung, G. (1997)
Related problems
- Minimal unsatisfiability/leanness
- Redundancy