2

A bit of context...

We are working on a project to convert FA (Finite Automata) to Digital Sequential Circuits and vice-versa.

In this process we came across a step: Reduction of Karnaugh (K-Maps).

Now, we are aware of the steps to be done when doing this manually by hand. But when it comes to implementing it as an algorithm, we found Quine-McCluskey which is a generalized algorithm for K-Map reduction.

Is Quine-McCluskey the best possible, most optimal way of doing that? or is there a more optimal way of doing that?

For example, when we talk about the Travelling Sales Man problem, we have various algorithms like Genetic, nearest neighbor, etc but they provide one of the optimal paths (locally optimal) paths, but not necessarily the most optimal path.

Dheeraj Lalwani
  • 23
  • 2

1 Answers1

3

Is Quine-McCluskey the best possible, most optimal way of doing that?

Yes. It is - it's a more machine-palatable way of doing it vs. Karnaugh maps that are mostly targeted for humans.

The problem is generally intractable. The computational complexity is exponential. For a finite automaton that's not a toy example, the computation won't finish in any reasonable time. So while the algorithm is optimal, it's not very useful for realistic problems.

So, the optimal way of doing it is almost irrelevant, since it's entirely impractical: that makes it practically sub-optimal. Yes, it provides optimal results, but the Universe will die before you get them if problems are of a non-trivial size.

There is a reason why Karnaugh maps are done by hand only on small problem sizes: for a problem just a few variables larger, you'd spend a year solving it manually, and even a computer will not finish in a reasonable time with practical problem sizes encountered in programmable logic design, compilers, etc.

So, in practice, you can't use the globally optimal algorithm, and must use approximations that provide locally optimal results: for the same reason that the Travelling Salesman problems of size practical enough the be of real utility can only be solved to yield non-global optima (at least not provably globally optimal).

Both logic simplification and traveling salesman are NP-complete problems, and the only "optimal" ways of solving them that we got are not better, in complexity terms, than an exhaustive enumeration of the solution space.

Kuba hasn't forgotten Monica
  • 32,734
  • 1
  • 38
  • 103
  • 1
    Good stuff. Also, I'd add that if the OP can formulate things well, a simulated annealing approach can be applied to these problems. But that said, there are almost uncounted papers on these optimization problems. This is a narrow field of study all of its own. One can dedicate a lifetime to it, if they want, and only elucidate out a few new ideas to add. It's a huge topic. And lots of people writing on it. – jonk Aug 02 '22 at 06:03
  • First of all, thank you so much for answering in such an elaborate way. Secondly, I get that in practicality, we cannot use the globally optimal algorithm if we have a problem with many variables. My question was is Quine-McCluskey a globally optimal algorithm, and if not, does there exist an algorithm which is globally optimal, even if we can't use it, does it exist? – Dheeraj Lalwani Aug 02 '22 at 12:05
  • Please reconsider your use of **optimal**, if it is not optimal but good enough there are other words to describe it. That casual use of the word makes your answer confusing, especially since you start with that quote "Is Quine-McCluskey the best possible, most optimal way of doing that?" to which you answer "Yes. It is" only to write "There is no "optimal" way of doing it in the sense that the problem is generally intractable". – jDAQ Aug 02 '22 at 16:56
  • 1
    @jDAQ I've edited it a bit, is this closer to what you had in mind? I genuinely want to improve this answer - as you've noted, it was a bit clunky. – Kuba hasn't forgotten Monica Aug 06 '22 at 00:13
  • 1
    Yes, I think it is clearer now that the algorithm does yield the optimal result but will take so long that it is not useful/feasible. – jDAQ Aug 06 '22 at 18:39