Which of the following is generally solved in polynomial time rather than being NP-Complete?

Options

  • A. Shortest Path Problem
  • B. 3-SAT Problem
  • C. Clique Problem
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

A. Shortest Path Problem

Detailed Explanation

The standard Shortest Path Problem is solvable in polynomial time and therefore belongs to P. For example, Dijkstra’s algorithm solves single-source shortest paths when edge weights are non-negative, while Bellman-Ford can handle negative edge weights provided there is no reachable negative cycle. In contrast, 3-SAT and Clique are standard NP-Complete problems. A key BPSC exam distinction is to recognize common polynomial-time graph algorithms versus computationally difficult decision problems.
← Previous Next →

Attempt Quiz Now:

BPSC TRE 4 DSA Practice set 1

Feature Posts