Vinay Deolalikar가 P! = NP라는 증거를 설명하십시오.
최근 HP Labs의 Vinay Deolalikar가 P! = NP를 증명했다고 주장 하는 논문 이 있습니다 .
누군가이 증명이 수학적으로 덜 경향이있는 사람들에게 어떻게 작용하는지 설명 할 수 있습니까?
나는 단지 종이를 훑어 봤지만, 여기에 모든 것이 어떻게 결합되는지에 대한 대략적인 요약이 있습니다.
논문의 86 페이지에서.
... 다항식 시간 알고리즘은 문제를 조건부 독립성을 통해 서로 결합되는 더 작은 하위 문제로 연속적으로 "분리"하여 성공합니다. 결과적으로 다항식 시간 알고리즘은 기본 문제 인스턴스와 순서가 동일한 블록이 동시 해결을 필요로하는 영역에서 문제를 해결할 수 없습니다.
논문의 다른 부분은 특정 NP 문제를 이러한 방식으로 분해 할 수 없음을 보여줍니다. 따라서 NP / = P
논문의 대부분은 조건부 독립성을 정의하고이 두 가지 사항을 증명하는 데 사용됩니다.
Dick Lipton은 논문에 대한 멋진 블로그 항목 과 그의 첫인상을 가지고 있습니다. 안타깝게도 기술적입니다. 내가 이해할 수있는 한 Deolalikar의 주요 혁신은 통계 물리학과 유한 모델 이론의 개념을 사용하여 문제와 연결하는 것 같습니다.
저는 Rex M과 함께 있습니다. 일부 결과는 기술 숙달이 부족한 사람들에게는 대부분 수학적 결과를 표현할 수 없습니다.
나는 이것을 좋아했다 ( http://www.newscientist.com/article/dn19287-p--np-its-bad-news-for-the-power-of-computing.html ) :
그의 주장은 특정 작업 인 부울 만족도 문제를 중심으로 전개됩니다.이 문제는 논리적 진술 모음이 모두 동시에 참일 수 있는지 또는 서로 모순되는지 여부를 묻습니다. 이것은 NP 문제로 알려져 있습니다.
Deolalikar는 처음부터 신속하게 완료 할 수있는 프로그램이 없으며 따라서 P 문제가 아니라고 주장합니다. 그의 주장은 통계 물리학의 독창적 인 사용과 관련이 있습니다. 그는 무작위 물리 시스템과 동일한 규칙을 많이 따르는 수학적 구조를 사용하기 때문입니다.
위의 효과는 매우 중요 할 수 있습니다.
결과가 유효하다면 두 클래스 P와 NP가 동일하지 않다는 것을 증명하고 컴퓨터가 수행 할 수있는 작업에 심각한 제한을 부과합니다. 이는 많은 작업이 근본적으로 환원 불가능하게 복잡 할 수 있음을 의미합니다.
인수 분해를 포함한 일부 문제의 경우 결과는 신속하게 해결할 수 있는지 여부를 명확하게 나타내지 않습니다. 그러나 "NP-complete"라고 불리는 거대한 하위 문제는 파멸 될 것입니다. 유명한 예는 여행하는 세일즈맨 문제입니다. 도시 집합 사이의 최단 경로를 찾는 것입니다. 이러한 문제는 빠르게 확인할 수 있지만 P ≠ NP라면 처음부터 빠르게 해결할 수있는 컴퓨터 프로그램이 없습니다.
이것이 증명 기술에 대한 나의 이해입니다. 그는 1 차 논리를 사용하여 모든 다항식 시간 알고리즘을 특성화 한 다음 특정 속성이있는 큰 SAT 문제의 경우 다항식 시간 알고리즘이 만족도를 결정할 수 없음을 보여줍니다.
완전히 틀렸을 수도 있지만 첫 번째 패스에서 읽은 첫인상은 또 하나의 생각입니다. 회로 만족도에서 용어를 할당 / 삭제하는 것은 '주문 된 그리고 그는 통계 물리학을 사용하여 다항식 연산의 특정 "단계 공간"에서 연산을 수행하기에 충분한 속도가 없다는 것을 보여줍니다. 왜냐하면이 "클러스터"가 너무 멀리 떨어져 있기 때문입니다.
이러한 증명은 지속적인 글로벌 최적화 와 같은 모든 종류의 알고리즘을 포함해야 합니다 .
예를 들어, 3-SAT 문제에서 우리는 이러한 변수의 트리플 또는 그 부정의 모든 대안을 충족하기 위해 변수를 평가해야합니다. x OR y최적화로 변경할 수있는 모습
((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2)
3 개의 변수를 대체 할 수있는 7 개의 항.
모든 항에 대해 이러한 다항식 합계의 전역 최소값을 찾는 것은 문제를 해결할 것입니다. ( 출처 )
_gradient 메서드, 로컬 최소화 제거 메서드, 진화 알고리즘을 사용하여 표준 조합 기술에서 연속 세계로 이동하고 있습니다. 그것은 완전히 다른 왕국입니다-수치 분석-그러한 증거가 실제로 덮을 수 있다고 생각하지 않습니다 (?)
증거로 "악마가 세부 사항에있다"는 점에 주목할 가치가 있습니다. 높은 수준의 개요는 분명히 다음과 같습니다.
어떤 종류의 항목 간의 관계는이 관계가 X를 의미하고 Y를 의미하므로 내 주장이 표시된다는 것을 보여줍니다.
내 말은, 그것은 인덕션 이나 다른 어떤 형태의 증명을 통해서 일 수도 있지만, 내가 말하는 것은 높은 수준의 개요는 쓸모 없다는 것입니다. 설명 할 필요가 없습니다. 질문 자체는 컴퓨터 과학과 관련이 있지만 수학자에게 맡기는 것이 가장 좋습니다 (확실히 매우 흥미 롭다고 생각합니다).
참고 URL : https://stackoverflow.com/questions/3436978/explain-the-proof-by-vinay-deolalikar-that-p-np
'programing tip' 카테고리의 다른 글
| Flutter : 상속 된 위젯을 올바르게 사용하는 방법? (0) | 2020.11.12 |
|---|---|
| 웹 페이지를 이미지로 변환 (0) | 2020.11.12 |
| mysql과 mysql2 gem의 차이점 (0) | 2020.11.12 |
| has_secure_password는 어떤 형태의 솔팅을 사용합니까? (0) | 2020.11.12 |
| “MapHttpRoute”와“MapRoute”의 차이점은 무엇입니까? (0) | 2020.11.12 |