Which of the following classes contains problems that can be solved in polynomial time?

Options

  • A. NP
  • B. NP-Hard
  • C. P
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

C. P

Detailed Explanation

  • P (Polynomial Time): Contains decision problems solvable by a deterministic Turing machine in polynomial time.
  • Examples: Sorting, shortest path, minimum spanning tree and primality testing.
  • Important: P is a subset of NP.