Logic optimization: Difference between revisions

Revision as of 04:52, 30 May 2022

Revision as of 09:46, 30 May 2022

Line 62:

The same methods of boolean expression minimization (simplification) listed below may be applied to the circuit optimization.

For the case when the Boolean function is specified by a circuit (that is, we want to find an equivalent circuit of minimum size possible), the unbounded circuit minimization problem was long-conjectured to be [[polynomial hierarchy|<math>\Sigma_2^P</math>-complete]]{{What|date=October 2021}}in [[time complexity]] (the complexity class of decision problems that can be solved on a deterministic Turing machine in polynomial time), a result finally proved in 2008,<ref name="Buchfuhrer_2011"/> but there are effective heuristics such as [[Karnaugh map]]s and the [[Quine–McCluskey algorithm]] that facilitate the process.

Boolean function minimizing methods include: