연구문헌
교육정보
심화정보
포커스iN
연구자료
- 문자 DB
- 용어사전
알림마당
CSERIC 광장

단어	Karp의 21 NP-COMPLETE 문제
단어	Karp’s 21 NP-complete problems
설명	계산 복잡도 이론의 가장 중요한 결과 중 하나는 Stephen Cook의 1971년 논문에서 NP-COMPLETE와 불의 만족 문제(Boolean satisfiability problem)이다. 1972년에 Richard Karp는 이러한 아이디어를 사용해서 논문 “Reducibility Among Combinatorial Problems”를 내놓았다. 이 논문에서 Richard Karp는 21개의 다양한 조합 문제와 그래프 이론 문제를 보였다. 여기에 나온 21개의 문제들은 모두 NP-COMPLETE로 다루기 힘든 문제로 손꼽혔다.