Content deleted Content added
Clarify |
|||
Line 53:
:Note that it is precisely the backtracking algorithm part of it that makes the solution exponential time - we're trying to solve the [[set cover problem]]. A heuristic strategy described in that article allows us to find a solution at worst ''ln n'' times larger than the minimum, where ''n'' is the largest number of original terms implied by any one prime implicant. [[User:Deco|Deco]] 06:51, 2 June 2006 (UTC)
::Er, slight accuracy fix: it might be possible the number of prime implicants itself could be much larger than the number of input terms, in which case other parts of the algorithm could be exponential time and so could heuristics in this stage. But this seems pretty unlikely for your average formula. [[User:Deco|Deco]] 07:08, 2 June 2006 (UTC)
== Question about the example ==
| |||