UTpaper

Free mock tests & test series

Question 135Asked in DSSSB PGT Computer Science (Technical), 11 Jul 2021

Which of the following isNot a NP Complete problem?

  1. AThe Clique problem
  2. BHamiltonian-Cycle problem
  3. CThe Travelling Salesman Problem
  4. DShortest Path Problem
Show answerHide answer

Correct answer: (D) Shortest Path Problem

Explanation

Shortest path is solvable in polynomial time (e.g., Dijkstra), so it is in P. Clique, Hamiltonian cycle and TSP (decision version) are NP-complete.

From DSSSB PGT Computer Science PYQ (Technical), 11 Jul 2021

This is question 135 of DSSSB PGT Computer Science PYQ (Technical), 11 Jul 2021. 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.