Given a truth table, find the smallest size circuit computing it. Recently it was shown that for multiple output function the problem MSCP (Minimum Size Circuit Problem) is NP-Complete. The article is available online see.

Question: What will be the impact of this problem? or I am not able to follow why this problem MSCP is so important?

I didn't read the article completely, only the introduction part, it seem to me that problem is related to many other problems of interest.

  • 1
    $\begingroup$ From the introduction: "Boolean circuit minimization is of high practical relevance, and a number of textbooks and monographs have been written about heuristics and other applied aspects of this problem (cf. [McC65, Sch01, HS06])." Did you try to follow these references to see why the problem is of practical interest? Also, the footnote gives different names for the same problem which you can use to look up information on Wikipedia like logic synthesis. The very first sentence of the abstract gives you a clear hint as well. $\endgroup$
    – Juho
    Feb 29 '20 at 13:00

Finding the minimum size circuit is not important in practice for large circuits. Finding small size circuits is of course important because it directly impacts the cost of building a circuit.

Finding minimum size circuits for small circuits that are used as building blocks is quite important. For example, you'd want to know how to build the smallest possible full adder if you end up having a million of them in a processor. And you really want a minimum size circuit for a bit of memory in your L3 cache when your processor has 36MB of L3 cache or 288 million of these cells.

However, minimising the delay of a circuit is also important, and sometimes more important or even far more important than minimum size.


Your Answer

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