You aim to design an efficient algorithm (polynomial complexity) to find the optimal (lowest) number of coins to give in the coin change problem. You realised that this is a combinatorial optimisation problem, and only brute-force algorithm can guarantee that you will find the optimal solution.

(1)Why does the brute-force algorithm does not satisfy efficiency requirement, in other words does not have a polynomial complexity?

(2)What complexity class this problem belongs to? What does that mean in terms of complexity to find a solution and verify it for this problem?