임인성 교수님이 가르친다는 과목을 들어본 적은 없으나, Chapter 2가 그런 제목이라면 NP-Completeness 이론의 고전적인 교과서인 <Computers and Intractability - A guide to the Theory of NP-Completeness> 라는 책입니다. Michael Garey와 David Johnson의 공저입니다. 출판사는 까먹었고, 79년도에 나온 책입니다. Johnson은 나중에 Journal of Algorithms에 NP-Completeness이론에 대한 칼럼을 연재하기도 했습니다. 그리고 현재에도 풀린 문제와 안풀린 문제를 심사하는 작업을 하고 있는 것으로 압니다. 맨 뒤쪽에 나오는 Open 문제들 중에 풀린것도 몇 개 있고 그냥 open으로 남아있는 것도 있습니다. 학부생들에게는 좀 어려울지도 모르겠으나 착실히 공부했다고 하거나 아니면 도전을 해보겠다고 하는 열정을 지닌 분들이라면 도전해볼만 합니다. 가장 좋은 것은 잘 아는 사람에게서 강의를 듣는 것입니다. 그리고 그런 문제들만 모아놓은게 있는데요. http://www.nada.kth.se/~viggo/problemlist/conpendium.html 방문해 보시길. --,--`-<@ 매일 그대와 아침햇살 받으며 매일 그대와 눈을 뜨고파.. 잠이 들고파.. Till the rivers flow up stream | Love is real \|||/ @@@ Till lovers cease to dream | Love is touch @|~j~|@ @^j^@ Till then, I'm yours, be mine | Love is free | ~ | @@ ~ @@