UTpaper

Free mock tests & test series

Question 38Asked in UGC NET Computer Science, December 2014 (Paper II & III, Selected Questions)

We can show that the clique problem is NP-hard by proving that :

  1. ACLIQUE ≤ₚ 3–CNF_SAT
  2. BCLIQUE ≤ₚ VERTEX_COVER
  3. CCLIQUE ≤ₚ SUBSET_SUM
  4. DNone of the above
Show answerHide answer

Correct answer: (D) None of the above

Explanation

To show CLIQUE is NP-hard, a known NP-complete problem must be reduced to CLIQUE (e.g. 3-CNF-SAT ≤ₚ CLIQUE), not the other way round. Reducing CLIQUE to 3-CNF-SAT, VERTEX_COVER or SUBSET_SUM only shows CLIQUE is no harder than them. So the answer is None of the above.

From UGC NET Computer Science PYQ, December 2014 (Paper II & III, Selected Questions)

This is question 38 of UGC NET Computer Science PYQ, December 2014 (Paper II & III, Selected Questions). 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.