쌍곡선 공간의 세포 오토마타에서 P = NP입니까?
나는 몇 년 전이 책 에서 NP 문제가 쌍곡면의 세포 자동 장치 공간에서 다루어 질 수 있다고 읽었습니다 . 이것은 무엇을 의미 하는가? 합니까 P = NP이 책 / 논문에 따르면?
논문에서 일부 발췌 :
이진 트리를 "무료"로 사용할 수 있다면 다항식 시간에 NP 문제를 해결할 수 있다는 것은 잘 알려져 있습니다 ([14, 5] 참조). 그러나 펜타 그리드에서 이진 트리 알고리즘을 구현하는 것은 즉각적인 것은 아니며이 섹션의 목표는 진행 방법을 나타내는 것입니다.
내 이해에서 P = NP 문제는 복잡한 문제를 해결하기 위해 다항식 시간 알고리즘을 찾고 있습니다. 책과 논문을 훑어 보면 그가 문제를 해결 한 것 같다. 내가 무엇을 놓치고 있습니까?
다음 은 In Some Curved Spaces, We Can Solve NP-Hard Problems in Polynomial Time : Towards Matiyasevich 's Dream 이라는 또 다른 논문 입니다.
답변
P 대 NP 문제는 튜링 머신에 대한 질문입니다. $T$, 복잡성 클래스 P와 NP는 이러한 이론적 기계의 관점에서 정의되기 때문입니다. 이 클래스를$P_T$ 과 $NP_T$지금부터. 이 논문은 새로운 이론적 계산 기계를 소개합니다$H$ 관련 클래스가있는 $P_H$ (쌍곡선 셀룰러 오토 마톤에서 다항식 시간으로 실행) $NP_H$ (쌍곡선 셀룰러 오토 마톤에서 비 결정적 다항식 시간으로 실행 됨).
이 백서의 첫 번째 단계는 잘 알려진 3SAT 문제를 증명하는 것입니다. $NP_T$-완전한 문제,이 기계에서 다항식 시간으로 풀 수 있습니다. 즉,이 문제는 $P_H$. 다음으로, Turing 기계에서 다항식 시간 단축이 쌍곡선 오토 마톤에서 다항식 시간으로 수행 될 수 있음을 보여줍니다. 3SAT는$NP_T$-완전, 모든 $NP_T$ 인스턴스는 다항식 시간에 3SAT 인스턴스로 축소 될 수 있습니다. $T$ 정의에 따라 $H$쌍곡선 오토 마톤에서 폴리 타임으로 3SAT를 풀면 해결됩니다. 즉,이 논문 (정리 1)의 주요 결과는 다음과 같이 쓸 수 있습니다.$NP_T \subseteq P_H$우리의 표기법에서. 이것은 P 대 NP 문제에 대한 해결책을 제공하지 않습니다.$NP_T$ 과 $P_T$.
저자는 섹션 4.2에서 P 대 NP 문제에 대한 몇 가지 언급을 포함하고 있으며, 여기서 결과가 P에 대한 증거라고 주장합니다.$\neq$NP (!) :
세 번째 방향은 일반적인 설정에서 P = NP 질문에 대한 새로운 빛으로 구성됩니다. 쌍곡선 공간은 유클리드 공간의 특성과 매우 다른 특성을 가지고 있으며, 특히 더 많은 방향을 가지고 있기 때문에 P를 증명하는 데 유리한 힌트가 아닐 것입니다.$\neq$유클리드 조건의 NP? 지난 10 년 동안 복잡성 분야의 작업은 사람들이 P를 더 많이 믿게하는 경향이있는 것 같습니다.$\neq$NP. 분명히 현재의 결과도 그 추세에 속합니다.