UTpaper

Free mock tests & test series

Question 4Asked in Bihar STET 2025 Paper II Computer Science, 3 Nov 2025, Shift 2 (2:00 PM) + 1 more paper

The concept of NP-Completeness was introduced by:

  1. AStephen Cook
  2. BRichard Karp
  3. CDonald Knuth
  4. DJohn Nash
Show answerHide answer

Correct answer: (B) Richard Karp

Explanation

Note: the answer key gives (B), but NP-completeness was introduced by Stephen Cook in 1971 (Cook-Levin theorem, SAT is NP-complete). Richard Karp in 1972 showed 21 other problems NP-complete and popularised the idea.

From Bihar STET 2025 Paper II Computer Science PYQ, 3 Nov 2025, Shift 2 (2:00 PM)

This is question 4 of Bihar STET 2025 Paper II Computer Science PYQ, 3 Nov 2025, Shift 2 (2:00 PM). 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.

Asked in 2 papers