Soundbite 답변 : DNA 컴퓨팅은 NP- 완전 문제를 해결하기위한 마술 지팡이를 제공하지 않습니다. 비록 1990 년대에 일부 존경받는 연구원들이 한동안 생각했을지라도 말입니다.

최초의 DNA 계산 실험은 유명한 수 이론가 Len Adleman이 이끄는 실험실에서 수행되었습니다. Adleman은 잘 알려진 NP- 완전 문제인 작은 Traveling Salesman Problem을 해결했으며 그와 다른 사람들은 그 방법이 확장 될 수있을 것으로 생각했습니다. Adleman 은이 짧은 비디오 에서 그의 접근 방식을 설명 합니다. 그들이 직면 한 문제는 적당한 크기의 TSP 문제를 해결하려면 지구 크기보다 더 많은 DNA가 필요하다는 것입니다. 그들은 동시에 수행되는 작업의 양을 늘림으로써 시간을 절약 할 수있는 방법을 찾았지만, 이것이 TSP 문제가 해결하기 위해 기하 급수적 인 자원보다 적게 요구한다는 것을 의미하지는 않습니다. 그들은 기하 급수적 비용을 시간 량에서 물리적 물질량으로 옮겼습니다.

(추가적인 질문이 있습니다 : 문제를 해결하기 위해 기하 급수적 인 기계가 필요한 경우, 기계를 구축하기 위해 기하 급수적 인 시간 또는 적어도 전처리가 자동으로 필요합니까? 그래도 한쪽 은요)

다른 일반적인 자원을 희생하여 계산에 필요한 시간을 줄이는이 일반적인 문제는 생물학적으로 영감을 얻은 컴퓨팅 모델에서 여러 번 나타났습니다. 멤브레인 컴퓨팅 (생물학적 세포의 추상화)에 관한 Wikipedia 페이지는 특정 유형의 멤브레인 시스템이 다항식 시간에 NP- 완전 문제를 해결할 수 있다고 말합니다. 이 시스템은 다항식 시간으로 전체 막 내부에 지수 적으로 많은 하위 객체를 만들 수 있기 때문에 작동합니다. 음 … 지수 적으로 많은 양의 원자재가 어떻게 외부 세계에서 일정한 표면적을 가진 막을 통해 들어오는가? 답 : 고려되지 않습니다. 그들은 계산에 필요한 자원을 지불하지 않습니다.

마지막으로, AHNEP를 보여주는 논문에 연결된 Anthony Labarre는 다항식 시간에 NP- 완전 문제를 해결할 수 있습니다. AHNEP가 3SAT를 선형으로 해결할 수 있음을 보여주는 논문도 있습니다.시각. AHNEP = 혁신적인 프로세서의 하이브리드 네트워크 수용. 진화 프로세서는 DNA에서 영감을 얻은 모델이며, 각 코어에는 각 단계에서 치환, 삭제 또는 (중요하게) 삽입에 의해 변경 될 수있는 문자열이 있습니다. 또한, 모든 노드에서 임의로 많은 수의 문자열을 사용할 수 있으며 각 통신 단계에서 모든 노드는 모든 올바른 문자열을 연결된 모든 노드로 보냅니다. 따라서 시간 비용이 들지 않으면 지수적인 양의 정보를 전송할 수 있으며 삽입 규칙으로 인해 개별 문자열이 계산 과정에서 더 커질 수 있으므로 두 번의 혼란이 있습니다.

최근 실제 컴퓨팅에 중점을 둔 연구자들이 최근 바이오 컴퓨팅 작업에 관심이있는 경우, 최근에 여러 영역에 대해 간략히 다루는 SIGACT News에 대해 쓴 이 서평을 제공 할 수 있습니다.

답변