Given a truth table, Find the smallest size circuit computing it. Recently it is 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 read the article not completely but only introduction part, it seem to me that problem is related to many other problems of interest.