Which of the following problems was the first problem proven to be NP-Complete?

Options

  • A. Boolean Satisfiability Problem (SAT)
  • B. Traveling Salesman Problem
  • C. Vertex Cover Problem
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

A. Boolean Satisfiability Problem (SAT)

Detailed Explanation

SAT, the Boolean Satisfiability Problem, was the first problem proven to be NP-Complete. The result is known as the Cook-Levin theorem. SAT asks whether there exists an assignment of Boolean values to variables that makes a given Boolean formula true. The importance of SAT is that every problem in NP can be transformed into SAT using a polynomial-time reduction. This established SAT as a fundamental problem in computational complexity theory and provided the foundation for the study of NP-Completeness.
← Previous Next →

Attempt Quiz Now:

BPSC TRE 4 DSA Practice set 1

Feature Posts