The first problem to be proven NP-Complete was the:एनपी-पूर्ण साबित होने वाली पहली समस्या थी:
एनपी-पूर्ण साबित होने वाली पहली समस्या थी:
Show answerHide answer
Correct answer: (C) Boolean Satisfiability Problem (SAT)बूलियन संतोषजनक समस्या (SAT)
Explanation
The Cook-Levin theorem (1971) proved Boolean Satisfiability (SAT) NP-complete. It was the first such problem, and others like TSP and Knapsack were later shown NP-complete by reduction from it.Cook-Levin प्रमेय (1971) ने Boolean Satisfiability (SAT) को NP-complete सिद्ध किया। यह ऐसी पहली समस्या थी, और TSP तथा Knapsack जैसी अन्य समस्याओं को बाद में इसी से reduction द्वारा NP-complete दिखाया गया।