목록P / NP 문제 (1)

NERD WORLD

컴퓨터과학이 여는 세계(이광근) - P/NP 문제

서울대학교 컴퓨터공학부 이광근 교수님이 쓰신, '컴퓨터과학이 여는 세계' 라는 책을 읽고 있다. 총 5장 중에서 4장 중반까지 읽었는데, 정말 훌륭한 교양 과학서라 생각한다. 책을 읽다보면 컴퓨터과학의 중요한 주제들이 연달아 등장한다. 이 중에서 블로그 포스트로 정리하고, 이해를 다져놓고 싶은 부분들에 대해서 간단히 정리한 것이다. 이 포스트로 해당 주제를 처음 접하는 사람을 위하기보다는, 내 자신의 이해를 다지기 위한 목적으로 포스트를 작성해볼 것이다.이번 포스트의 주제는 'P = NP 문제' 이다. 컴퓨터과학에서 매우 중요한 문제 중 하나이다. 이 문제를 푼다면, 아마 컴퓨터과학계의 노벨상이라 불리는 튜링상은 따논 당상 아닐까....용어 정의를 통해서 개념을 잡아보도록 하자. 컴퓨터로 풀 수 있는 문..
일상 2016. 4. 12. 17:50
Prev 1 Next