수학적 도구/Theory of computation (2) 썸네일형 리스트형 NP-완전 이해하기 (NP-Completeness) 지난번에 이어 이번에도 컴퓨터 과학의 최대 난제인 P vs NP에 대해서 좀더 깊게 들어가 보겠습니다. 이전 포스트에서는 P와 NP가 각각 직관적으로 어떤 의미를 갖고 있는지에 대해서 알아 보았는데요. 이를 보다 엄밀히 정의하면 다음과 같습니다. P는 다항 시간(polynomial time)에 결정론적(deterministically)으로 해결 가능한(solvable) 문제들의 집합입니다. 다시 말해, 어떤 결정 문제(decision problem) \(X\)에 대해, 주어지는 입력(input)이 참인지 거짓인지를 다항 시간에 결정론적으로 해결하는 알고리즘이 존재하면 \(X \in \mathrm{P}\)입니다. NP는 다항 시간에 비결정론적(nondeterministically)으로 해결 가능한 문제들의.. P vs NP 쉽게 이해하기 컴퓨터 과학에는 유명한 난제가 있습니다. 바로 P vs NP입니다. 컴퓨터 과학을 공부하다 보면 언젠간 한 번은 반드시 접하게 되는 흥미롭고도 신기한 문제인데요. 이번 포스트에서는 이에 대해서 함께 알아보도록 하겠습니다. 저는 P vs NP 문제를 대학생 시절 알고리즘 수업을 들을 때 처음 접하였습니다. 솔직히 말씀드리면, 당시에는 진짜 하나도 이해를 못했다고 해도 과언이 아니었습니다. P, NP 내용이 기말고사 범위였는데, 시험 볼 때는 교과서나 강의 자료의 내용을 그저 달달 외워서 베껴 적었던 기억이 나네요. 그 후 대학원 준비를 할 때 P와 NP에 대해서 좀더 알게 되었고, 진학 후에야 그것들을 제대로 이해하는 수준에 이르렀습니다. 그만큼 어렵게 배운 개념이었는데요. 막상 제대로 이해를 한 후에는 .. 이전 1 다음
