Content deleted Content added
→Methods: clarity? Tags: Mobile edit Mobile app edit Android app edit |
→Methods: Added links, it lists a bunch of other documents, I don't know the protocol for adding references that add references?! Tags: Reverted Mobile edit Mobile app edit Android app edit |
||
Line 60:
=== {{Anchor|Circuit minimization in Boolean algebra}}Boolean expression minimization ===
{{Clean up|date=October 2021|reason=We need more consistent, simpler and prose-like summary on every method|section}}
The same methods of boolean expression minimization (simplification) listed below may be applied to the [[circuit complexity]] optimization.<ref>https://csrc.nist.gov/Projects/circuit-complexity.</ref>
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]] 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.
| |||