Solution

The correct answer is A, B and C only

Key Points

• Statement A: "If some NP-complete problem P is in P then P = NP" is correct.
  • It states that if you can come up with a polynomial-time algorithm for a single NP-complete problem, then that would mean all NP problems have polynomial-time solutions -- that is, P would equal NP. This is the definition of NP-completeness.
• Statement B: "TSP is in NP" is correct.
  • The Travelling Salesman Problem (TSP) is indeed an NP problem: given a list of cities and the distances between them, find the shortest possible route that visits each city and returns to the origin city. It can be verified quickly, but we do not have a quick solution on how to solve it.
• Statement C: "SAT is in NP" is correct as well.
  • The Boolean satisfiability problem (SAT) is a decision problem, whose instance is a Boolean expression written using only AND, OR, NOT, variables, and parentheses. The question is: given the expression, is there some assignment of TRUE and FALSE values to the variables that will make the entire expression true? A SAT instance can be checked quickly, but again, we have no quick algorithm to solve it.
• Statement D: "Hamilton circuit problem is not NP-complete" is incorrect.
  • The Hamiltonian circuit problem, which is finding a path in a graph that visits every vertex exactly once and returns to the original vertex, is a classic example of an NP-complete problem