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.