Content deleted Content added
Tags: Mobile edit Mobile web edit |
|||
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
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"/>
| |||