Which of the following is NOT an NP-Complete problem?

Asked In: BPSC TRE 3.0

Options

  • A. Traveling Salesman Problem
  • B. Boolean Satisfiability Problem
  • C. Shortest Path Problem
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

C. Shortest Path Problem

Detailed Explanation

NP-Complete problems are problems that are both in NP and NP-hard. The decision version of the Traveling Salesman Problem (TSP) and the Boolean Satisfiability Problem (SAT) are standard NP-Complete problems. In contrast, the Shortest Path Problem can be solved in polynomial time using algorithms such as Dijkstra’s algorithm for suitable edge weights and Bellman-Ford when negative edges are present. Therefore, Shortest Path is generally classified in P, not NP-Complete.
← Previous Next →

Attempt Quiz Now:

BPSC TRE 4 DSA Practice set 1

Feature Posts