2
\$\begingroup\$

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.

\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

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.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – jonk
    Aug 2 at 6:03
  • \$\begingroup\$ 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? \$\endgroup\$ Aug 2 at 12:05
  • \$\begingroup\$ 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". \$\endgroup\$
    – jDAQ
    Aug 2 at 16:56
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Aug 6 at 0:13
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – jDAQ
    Aug 6 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.