| [ sciEncE ] in KIDS 글 쓴 이(By): jeehk (me) 날 짜 (Date): 2003년 7월 13일 일요일 오전 08시 25분 12초 제 목(Title): [q] quantum computer와 DNA computer 우선 앞에서 울프램의 a new kind of science에 대해 답변 주신 분들께 감사드리고요 양자 컴퓨터나 DNA 컴퓨터를 사용하는 경우, NP class의 문제들을 효과적으로 (다항 시간 내에) 풀 수 있... 을 가능성이 있다는 얘기를 많이 들었습니다. (양자 컴퓨터에서 잘하면 P=NP 일수도 있다더군요) 예전에 어디선가 보기로는 DNA를 이용해서 TSP 문제를 푸는 시도를 한 사람들도 있다고 하고, 양자 컴퓨터에선 선형 탐색이 O(N) 이 아니라 O(log N) 에 된다는 얘기도 듣기는 했는데... 현대물리나 생물학에 문외한인 저로서는 어떻게 NP가 풀리는지 감이 잘 오질 않습니다. 양자 컴퓨터의 nondeterministic(=probabilistic?) 한 성질과 DNA 컴퓨터의 massive parallelism 이 key point 일 것 같은데, 그렇다고 해도 NP 문제가 풀린다는 것에 대해선 감이 오질 않네요. 이걸 비전문가에게 감이 오게 설명해 주실 분이 계신지요? p.s. 이런 새로운 방식의 컴퓨터들과 Turing machine과의 관계도 알고 시퍼요 p.s.2. 미래에 인간 두뇌가 기계로 구현된다면, 이런 기술들이 쓰이게 될까요? |