Content deleted Content added
Undid revision 1278621291 by 58.186.69.102 (talk) |
Citation bot (talk | contribs) Add: isbn, pages, volume, series. | Use this bot. Report bugs. | Suggested by Ringo62 | Category:Boolean algebra | #UCB_Category 84/103 |
||
Line 12:
==Complexity==
Although more practical than [[Karnaugh mapping]] when dealing with more than four variables, the Quine–McCluskey algorithm also has a limited range of use since the [[Boolean satisfiability problem|problem]] it solves is [[NP-complete]].<ref name="Masek_1979"/><ref name="Czort_1999"/><ref name="Umans_2006"/> The [[running time]] of the Quine–McCluskey algorithm grows [[exponential growth|exponentially]] with the number of variables. For a function of ''n'' variables the number of prime implicants can be as large as <math>3^n/\sqrt{n}</math> ,<ref name="ChandraMarkowsky_1978"/> e.g. for 32 variables there may be over 534 × 10<sup>12</sup> prime implicants. Functions with a large number of variables have to be minimized with potentially non-optimal [[Heuristic algorithm|heuristic]] methods, of which the [[Espresso heuristic logic minimizer]] was the de facto standard in 1995.{{update inline|date=May 2017|reason=The reference correctly describes the situation in 1995. We need to expand this to include the changes of the past twenty years, however.}}<ref name="Nelson_1995"/> For one natural class of functions <math>f</math>, the precise complexity of finding all prime implicants is better-understood: Milan Mossé, Harry Sha, and Li-Yang Tan discovered a near-optimal algorithm for finding all prime implicants of a formula in [[conjunctive normal form]].<ref>{{Cite journal |last1=Mossé |first1=Milan |last2=Sha |first2=Harry |last3=Tan |first3=Li-Yang |date=2022 |title=A Generalization of the Satisfiability Coding Lemma and Its Applications |journal=DROPS-IDN/V2/Document/10.4230/LIPIcs.SAT.2022.9 |series=Leibniz International Proceedings in Informatics (LIPIcs) |volume=236 |pages=9:1–9:18 |language=en |publisher=Schloss Dagstuhl – Leibniz-Zentrum für Informatik |doi=10.4230/LIPIcs.SAT.2022.9|doi-access=free |isbn=978-3-95977-242-6 }}</ref>
Step two of the algorithm amounts to solving the [[set cover problem]];<ref name="Feldman_2009"/> [[NP-hard]] instances of this problem may occur in this algorithm step.<ref name="Gimpel_1965"/><ref name="Paul_1974"/>
| |||