Meanings of NP-completeness Reduce the number of questions without increasing the number of answers. Huge impacts on almost all other sciences such as physics,chemistry,biology,.. o Now given a computational problem in NP,the first step is usually to see whether it's in P or NPC "The biggest export of Theoretical Computer Science.” 16Meanings of NP-completeness ◼ Reduce the number of questions without increasing the number of answers. ◼ Huge impacts on almost all other sciences such as physics, chemistry, biology, … ❑ Now given a computational problem in NP, the first step is usually to see whether it’s in P or NPC. ◼ “The biggest export of Theoretical Computer Science.” 16