UTpaper

Free mock tests & test series

Question 102Asked in BPSC TRE 3.0 (2024) Computer Science Class 11-12

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

  1. ATraveling Salesman Problem
  2. BBoolean Satisfiability Problem
  3. CShortest Path Problem
  4. DMore than one of the above
  5. ENone of the above
Show answerHide answer

Correct answer: (C) Shortest Path Problem

Explanation

The shortest path problem can be solved in polynomial time (for example with Dijkstra's algorithm), so it is not NP-complete. TSP (decision version) and SAT are NP-complete.

From BPSC TRE 3.0 (2024) Computer Science Class 11-12 — Previous Year Paper

This is question 102 of BPSC TRE 3.0 (2024) Computer Science Class 11-12 — Previous Year Paper. See all questions of this paper with answers, or attempt the paper as a timed online test to get your score and all-India rank.