1. Please explain “NP-completeness (NPC)” and give several NPC problems. (25%)

4. Recently, major CPU manufacturers announce new APU (Accelerated Processing Unit) products to the market for the next-generation computers. Please state what an APU is and why it is the emerging trend of future computers. (25%)