P=NP (1) 썸네일형 리스트형 근사 알고리즘 (Approximation Algorithm) 현대 사회는 컴퓨터와 떼어낼 수 없는 관계를 맺고 있습니다. 우리는 컴퓨터를 통해 문제를 해결하고, 다른 이들과 소통하며, 여가를 즐기기도 합니다. 그렇다면, 과연 컴퓨터는 모든 것을 해줄 수 있을까요? 아시는 분들은 아시겠지만, 컴퓨터가 모든 것을 해결해 줄 수는 없습니다. 가장 유명한 예시로는 halting problem이 있습니다. 이는 어떤 컴퓨터 프로그램과 그 프로그램의 한 입력이 주어졌을 때, 프로그램이 언젠간 끝이 나는지 아니면 영원히 동작할지를 판단하는 문제입니다. 저명한 수학자 Alan Turing은 이 문제가 컴퓨터로는, 좀 더 정확히는 Turing machine으로는, 해결할 수 없다는 것을 증명하였습니다. 이번에는 약간 결이 다른 이야기를 해보겠습니다. 여러분들이 유명 밴드의 매니저.. 이전 1 다음
