이 p! = np 증명에 대해 누락 된 것은 무엇입니까?

Question

비밀번호를 복구하려고했습니다. 이것을 생각할 때 나는 "비밀번호 복구"문제가 NP 문제의 아주 좋은 예라는 것을 인식했습니다. 비밀번호를 알고 있다면 다항식 시간에 확인하기가 매우 쉽습니다. 그러나 비밀번호를 모르는 경우 가능한 솔루션의 전체 공간을 검색해야하며 지수 시간이 걸릴 수 있습니다.

이제 내 질문은 : "비밀번호 복구"이후 p! = np가 실행하는 데 다항식 시간 이상이 필요하다는 것을 보여줄 수있는 NP의 요소라는 것을 보여주지 않습니까?

Answer 1

문제는 비밀번호 복구가 비 동간성이라는 것을 보여주지 않습니다. 분명히 기하 급수적 인 답변 공간을 검색해야하기 때문입니다.

실제로 "Password Recovery"는 실제로 표준에 대한 설명이 아닙니다. 계산 문제. 공식적으로 암호 브레이킹 알고리즘은 주어진 문자열이 올바른 비밀번호인지 여부에 답할 수있는 일종의 "Oracle"을 사용하는 것 같습니다. 그러나 P 및 NP는 문자열을 입력으로 사용하는 튜링 머신의 관점에서 정의됩니다.

Answer 2

당신이 그것을 보여 주면 어느 "비밀번호 복구"를 해결하는 알고리즘에는 다항식 시간 이상이 필요하며 P ≠ NP임을 보여줍니다.

그렇지 않으면, 당신이 그것을 보여 주면 하나의 특정 솔루션 다항식 시간 이상이 필요하며 아무것도 보여주지 않습니다. 지수 시간이 필요한 종류 (정렬 될 때까지 셔플 어레이)을 쓸 수 있지만, 다항식 솔루션이 없다는 것은 아닙니다.

Answer 3

NP는 그것이 당신이 생각하고 있던 것 (그리고 당신이 그렇지 않은 경우 미리 사과드립니다)이라면 "비 종교적"을 의미하지는 않습니다. 그것은 "비 결정적 다항식"을 의미합니다. 비 결정적 알고리즘은 알고리즘의 무한한 평행 인스턴스와 동일한 알고리즘입니다. 예를 들어, Brute Force로 올바른 암호를 찾는 것은 비정상적인 다항식입니다. 암호를 확인하는 것이 정확한 경우, 추측이 정확하면 암호 길이에 선형 (즉, 다항식) 시간이 걸리지 만 필요합니다. 임의의 가능한 비밀번호 (k^n)를 동시에 확인한 다음이 방법을 사용하여 솔루션을 찾는 데 드는 비용은 비 결정적 다항식입니다.

비 결정적 알고리즘은 또한 어떤 단계에서 상태가 분지하는 사람을 생각할 수 있습니다. 이것의 간단한 예는 비 결정적 유한 한 유한 자동화 (NFA)입니다. 때로는 상태간에 어떤 우위가 무엇인지 알지 못하므로 둘 다 가져갑니다. 모든 NFA가 결정 론적 FA와 동일하다는 것을 쉽게 보여주기 쉽기 때문에 다른 흥미로운 클래스의 알고리즘에 대해서도 동일하게 입증 될 수 있다고 생각하는 것이 좋습니다. 불행히도 다항식 알고리즘의 일반적인 경우에는 그렇게하기가 어렵고, 일반적인 의심은 그것들이 동등하지 않다는 것입니다. 즉, p! = np.

Answer 4

문제가 NP에 있다는 이유는 정확합니다. 다항식 시간에 확인할 수 있다면 NP에 있습니다. 매우 간단한 문제조차도 NP에 있습니다. 기본적으로 모든 P는 NP에 포함됩니다. (*)

자, 여기에 이것을 p! = np :이 증거로 바꿀 수있는 한 가지 방법이 있습니다.

1) "비밀번호 복구"가 NP- 완성임을 보여줍니다. 즉, NP의 모든 문제는 다항식 시간에 "비밀번호 복구"로 줄일 수 있습니다. (즉, 다른 NP 문제를 "비밀번호 복구"로 변환하는 효율적인 알고리즘이 있습니다.)

2) Pavel Shved가 언급 한 것처럼 직관적 인 알고리즘이 비 뇌성이라는 것을 보여주는 것만으로는 충분하지 않습니다. "비밀번호 복구"를 해결하기 위해 다항식 알고리즘이 존재하지 않음을 보여 주어야합니다. 매우 어려운 작업.

(*) Edmund도 옳습니다. NP는 비 결정적 기계의 다항식을 의미합니다. 다항식 검증은 본질적으로 비 결정적 기계에 의해 선택된 경로입니다.

Answer 5

1. 언급 한 바와 같이, "비밀번호 복구"는 의사 결정 문제가 아닙니다.
2. "비밀번호 복구"에 다항식 시간 알고리즘이 없다는 것을 증명하지 않았으며 직관적 인 근거에 대해서만 주장하지 않았다. 솔루션 공간이 거대한다고해서 솔루션을 찾는 빠른 알고리즘이 없다는 것을 의미하지는 않습니다. 예를 들어, 있습니다 n! 세트의 순열 n 독특한 정수이지만 하나만 오름차순으로 분류되지만 우리는 그것을 찾을 수 있습니다. n log n 시각. 더 재미있는 예는 참조하십시오 프로젝트 오일러 #67.
3. "비밀번호 복구"를 의사 결정 문제로 바꾸고 해결하기위한 다항식 시간 알고리즘이 없음을 보여줄 수 있었음에도 불구하고 이제 "비밀번호 복구"가 NP- 완성임을 증명해야합니다.

P/NP/등에 대한 자세한 내용은 이것 좀 봐 이전 질문.

Answer 6

이 문제에 대한 공식적인 진술은 해시 값 (및 소금)을 입력하고 찾으려는 시도로 받아들이는 것입니다. ㅏ 해시를 생성하는 비밀번호 : 기본 알려진 Cyphertext Collision 찾기 문제.

해시의 품질에 따라 이것 그렇지 않을 수 있습니다 지수 시간이 필요합니다. 실제로, 널리 사용되는 많은 암호화 해시는 키 스페이스 검색보다 더 빠른 공격을 확인했습니다.

즉, 당신 (다른 응답자 중 일부)은 추정 비밀번호 munging 루틴에는 디자이너가 원했던 모든 속성이 있습니다. 이것은해야 할 것입니다 증명되었습니다.

Answer 7

이 대답을 작성하는 것은 어느 시점 에서이 아이디어를 가지고 있었기 때문에 여기에 대한 답변은 만족스럽지 않았습니다.

당신은 '오라클'의 존재하에 p =/= np임을 증명했습니다 (이것은 암호가 옳은지 아닌지를 알려주는 것입니다).

Oracles를 사용하여 원래 P VS NP를 실제로 증명할 수 없다는 것이 밝혀졌습니다 (이 기술을 상대성이라고 함).

원래의 문제를 증명하려면 튜링 머신의 관점에서 오라클을 정의해야합니다. 다시 말해, 암호 검증자가 입력으로 수행하는 작업을 설명한 다음 비밀번호 검증기 코드가 주어진 비밀번호를 추측 할 수있는 알고리즘이 없음을 증명해야합니다.

가능한 빠른 비밀번호 검증자를 위해이 작업을 수행해야합니다. 비밀번호 검증 자 알고리즘의 유일한 요구 사항은 비밀번호 길이와 관련하여 폴리 언어 시간에 실행된다는 것입니다.

따라서 비밀번호가 폴리 언어 시간인지 여부를 확인하는 가능한 알고리즘이 주어지면 검증 자 알고리즘을 읽고 암호가 폴리 언어 시간이라고 추측하는 알고리즘을 작성해야합니다. 그러한 알고리즘이 존재한다는 것을 증명하거나 반증 할 수 있다면 문제를 해결했습니다.