P대 NP문제에 대해서

[머슴(219.255)]

P대 NP문제에 대해서 이해하기 위해서는 수학의 어느분야의 지식을 가지고 있어야 하나요? 그리고 이 문제에 대해서 잘 설명해놓은 책이 있다면 추천해주시면 감사하겠습니다.

[수학동자(155.230)]

컴퓨터 공학과/수학과 개설과목 중에 "형식언어와 계산이론"이라는 과목이 있습니다. 학교에 따라 약간씩 다르지만 대충 이런 제목의...... 영어로는 "Theofy of Computation"이라고 하지요. 이런 과목들을 공부하면 P vs NP에 대한 기초적인 개념을 알 수 있습니다. 인터넷에서 "Computaion Theory" 로 검색하셈...

[수학동자(155.230)]

위에 "Theofy"는 오타... 원서로는 Hopcroft & Ullman의 "Introduction to Automata Theory, Languages, and Computation"를 본좌로 치는거 같던데...(아마존 닭컴 리뷰 기준) 이쪽 분야 책은 번역된게 많지 않고, Peter Linz라는 사람 교과서가 번역돼 있는걸로 압니다. 참고하셈..

[머슴(164.125)]

수학동자님 친절하신답변에 감사드려염