“P = NP”란 무엇이며 왜 그렇게 유명한 질문입니까?

“P = NP”란 무엇이며 왜 그렇게 유명한 질문입니까? [닫은]

---

P = NP가 아마도 모든 컴퓨터 과학에서 가장 유명한 지에 대한 질문. 무슨 뜻인가요? 왜 그렇게 재미 있습니까?

아, 그리고 추가 신용을 위해 진술의 진실 또는 허위에 대한 증거를 게시하십시오. :)

---

P는 다항식 시간을 나타냅니다. NP는 비 결정적 다항식 시간을 나타냅니다.

정의 :

• 다항식 시간 은 알고리즘의 복잡도가 O (n ^ k)임을 의미합니다. 여기서 n은 데이터 크기 (예 : 정렬 할 목록의 요소 수)이고 k는 상수입니다.

• 복잡성 은 데이터 항목 수의 함수로 수행 할 작업 수에서 측정 된 시간입니다.

• 작업 은 특정 작업의 기본 작업으로 의미가있는 것입니다. 기본 작업 정렬은 비교입니다. 행렬 곱셈의 경우 기본 연산은 두 숫자의 곱입니다.

이제 결정 론적 의미와 비결정론 적 의미는 무엇입니까? Turing machine (TM)이라는 가상 컴퓨터 인 추상 계산 모델이 있습니다. 이 기계는 유한 한 수의 상태와, 유한 한 테이프 세트를 쓰고 읽을 수있는 개별 셀이있는 무한 테이프를 가지고 있습니다. 주어진 시간에 TM은 상태 중 하나에 있으며 테이프의 특정 셀을보고 있습니다. 해당 셀에서 읽은 내용에 따라 해당 셀에 새 심볼을 작성하고 테이프를 한 셀 앞뒤로 이동 한 다음 다른 상태로 이동할 수 있습니다. 이것을 상태 전이라고합니다. 놀랍게도 상태와 전환을 신중하게 구성하여 작성할 수있는 모든 컴퓨터 프로그램에 해당하는 TM을 설계 할 수 있습니다.

여기에는 우리가 관심을 갖는 두 가지 종류의 TM이 있습니다 : 결정 론적 및 비결정론 적. 결정 성 TM은 테이프를 읽는 각 기호에 대해 각 상태에서 하나의 전이만 갖습니다. 비 결정적 TM은 그러한 전이를 여러 개 가질 수있다. 즉, 여러 가능성을 동시에 확인할 수있다. 이것은 여러 스레드를 생성하는 것과 같습니다. 차이점은 비 결정적 TM이 원하는만큼의 "스레드"를 생성 할 수 있고 실제 컴퓨터에서는 특정 수의 스레드 만 한 번에 실행될 수 있다는 것입니다 (CPU 수와 동일). 실제로 컴퓨터는 기본적으로 유한 테이프를 갖춘 결정 론적 TM입니다. 한편, 양자 컴퓨터를 제외하고는 비 결정적 TM을 물리적으로 실현할 수 없습니다.

비 결정적 TM에 의해 해결 될 수있는 모든 문제는 결정적 TM에 의해 해결 될 수 있음이 입증되었다. 그러나 시간이 얼마나 걸리는지 명확하지 않습니다. 문장 P = NP는 문제가 비 결정적 TM에 대해 다항식 시간이 걸리면 다항식 시간에서도 동일한 문제를 해결할 결정적 TM을 작성할 수 있음을 의미합니다. 지금까지 아무도 그 일을 할 수 있다는 것을 보여줄 수 없었지만, 그 일도 할 수 없다는 것을 증명할 수 없었습니다.

NP- 완전 문제는 NP 문제 X를 의미하므로 다항식 감소에 의해 NP 문제 Y를 X로 줄일 수 있습니다. 즉, NP 완료 문제에 대한 다항식 솔루션을 만든 사람이라면 NP 문제에 대한 다항식 솔루션도 제공 될 것입니다. 따라서 그것은 P = NP임을 증명할 것입니다. 반대로, 누군가 P! = NP임을 증명한다면, 일반적인 컴퓨터에서 다항식 시간으로 NP 문제를 해결할 방법이 없다는 것을 확신 할 수 있습니다.

NP- 완전 문제의 예는 n 개의 변수를 포함하는 부울 식을 true로 만드는 진리 할당을 찾는 문제입니다.
실제로는 비 결정적 TM에서 다항식 시간이 걸리는 모든 문제는 결정적 TM 또는 일반 컴퓨터에서 지수 시간으로 만 수행 할 수 있습니다.
예를 들어, 진실 할당 문제를 해결하는 유일한 방법은 2 ^ n 가능성을 시도하는 것입니다.

---

1. 다항식 시간으로 답을 계산할 수 있으면 예 ( 아니오) 문제는 P ( P olynomial time)에 있습니다.
2. A 예 - 나 - 아무 문제에없는 NP ( N 에 결정적 P 찬성 대답이 될 수있는 경우 olynomial 시간) 확인 다항식 시간에.

직관적으로, 우리는 문제가있는 경우 볼 수 있습니다 P , 다음은에 NP . P 의 문제에 대한 잠재적 인 답변이 주어지면 간단히 답을 다시 계산하여 답변을 확인할 수 있습니다.

NP의 모든 문제 가 P 에 있는지 여부는 덜 분명하고 대답하기가 훨씬 어렵습니다 . 다항식 시간으로 답을 확인할 수 있다는 사실이 다항식 시간으로 그 답을 계산할 수 있다는 의미입니까?

NP- 완료 로 알려진 많은 중요한 문제가 있습니다 (기본적으로 이러한 문제가 P 로 입증 된 경우 모든 NP 문제는 P 로 입증 됨 ). 경우 P는 = NP를 , 모든 이러한 문제를 효율적으로 (다항식 시간) 솔루션을 입증한다.

대부분의 과학자들은 P ! = NP 라고 생각합니다 . 그러나 P = NP 또는 P ! = NP에 대한 증거는 아직 확립되지 않았습니다 . 누군가가 어느 쪽의 추측에 대한 증거를 제공한다면, 그들은 백만 달러를 이길 것 입니다.

---

가장 간단한 대답을하기 위해 :

특정 수의 입력을 취하는 문제가 있고 주어진 입력에 대한 문제를 해결할 수도 있고 해결할 수없는 다양한 솔루션이 있다고 가정합니다. 퍼즐 매거진의 논리 퍼즐은 좋은 예입니다. 입력은 조건 ( "George는 청록색 또는 녹색 집에 살지 않습니다")이며 잠재적 해결책은 진술 목록입니다 ( "George는 노란색으로 산다" 집, 완두콩을 키우고 개를 소유합니다 "). 유명한 예는 Traveling Salesman 문제입니다. 도시 목록과 도시에서 다른 도시로 이동하는 시간과 시간 제한을 고려할 때 잠재적 해결책은 판매원이 방문한 순서대로 도시 목록이 될 것입니다. 여행 시간의 합이 시간 제한보다 작 으면 작동합니다.

잠재적 인 솔루션을 효율적으로 검사하여 작동하는지 확인할 수 있다면 이러한 문제는 NP에 있습니다. 예를 들어, 세일즈맨이 방문 할 도시 목록을 순서대로 살펴보면 각 도시 간 여행 시간을 합산하여 시간 제한 미만인지 쉽게 확인할 수 있습니다. 솔루션이 존재하는 경우 효율적으로 찾을 수 있으면 문제는 P에 있습니다.

(효율적으로 여기에는 정확한 수학적 의미가 있습니다. 실제로 큰 문제를 해결하기가 어렵지 않다는 것을 의미합니다. 가능한 솔루션을 검색 할 때 가능한 모든 잠재적 인 솔루션이나 그에 가까운 것을 나열하는 비효율적 인 방법이 있습니다. 효율적인 방법을 사용하려면 훨씬 제한된 세트를 검색해야합니다.)

따라서 P = NP 문제는 다음과 같이 표현할 수 있습니다. 위에서 설명한 종류의 문제에 대한 솔루션을 효율적으로 검증 할 수 있다면 솔루션을 효율적으로 찾거나 찾을 수 없습니까? 명백한 대답은 "왜 당신이 할 수 있어야 하는가?"이며, 그것은 오늘날 문제가있는 곳과 거의 같습니다. 어느 누구도 그것을 증명할 수 없었으며 많은 수학자와 컴퓨터 과학자들을 귀찮게한다. 이것이 솔루션을 입증 할 수있는 사람이 Claypool Foundation의 백만 달러에 달하는 이유입니다.

일반적으로 P는 NP와 같지 않으며 솔루션을 찾을 수있는 일반적인 방법이 없다고 가정합니다. P = NP 인 것으로 판명되면 많은 것이 변할 것입니다. 예를 들어, 암호화는 불가능 해졌으며 인터넷에서 모든 종류의 개인 정보 보호 또는 확인이 가능해졌습니다. 결국 암호화 된 텍스트와 키를 효율적으로 가져 와서 원본 텍스트를 생성 할 수 있으므로 P = NP 인 경우 미리 알 필요없이 키를 효율적으로 찾을 수 있습니다. 비밀번호 크래킹은 사소한 것이 될 것입니다. 반면에 효과적으로 해결할 수있는 계획 문제와 리소스 할당 문제의 전체 클래스가 있습니다.

NP-complete라는 설명을 들었을 수 있습니다. NP- 완전 문제는 NP (물론)이며 다음과 같은 흥미로운 특성을 가지고 있습니다. 문제가 P에 있으면 모든 NP 문제는 P이므로 NP = NP입니다. Traveling Salesman 문제 또는 퍼즐 매거진의 논리 퍼즐을 효율적으로 해결하는 방법을 찾을 수 있다면 NP의 모든 것을 효율적으로 해결할 수 있습니다. NP- 완전 문제는 어떤면에서 가장 어려운 NP 문제입니다.

따라서 NP 완료 문제에 대한 효율적인 일반 솔루션 기술을 찾거나 그러한 기술이 존재하지 않음을 증명할 수 있다면 명성과 재산은 당신의 것입니다.

---

나의 겸손한 지식으로부터의 짧은 요약 :

매우 빠른 계산이 가능한 몇 가지 쉬운 계산 문제가 있습니다 (그래프에서 두 점 사이의 최단 경로 찾기) (O (n ^ k), 여기서 n은 입력 크기이고 k는 상수입니다 그래프의 경우 정점 또는 모서리 수)).

그래프의 모든 정점을 가로 지르는 경로를 찾거나 공개 키에서 RSA 개인 키를 얻는 것과 같은 다른 문제는 더 어렵습니다 (O (e ^ n)).

그러나 CS의 말에 따르면 문제는 비결정론 적 튜링 머신을 결정 론적 머신으로 '변환'할 수는 없지만 정규 표현식 파서와 같은 비결정론 적 유한 오토 마톤을 결정 론적 오토 마틱으로 변환 할 수 있다는 것입니다. 할 수는 있지만 기계의 실행 시간이 오래 걸립니다). 즉, 가능한 모든 경로를 시도해야합니다 (보통 똑똑한 CS 교수는 몇 가지를 제외 할 수 있음).

아무도 해결책에 대해 전혀 알지 못하기 때문에 흥미 롭습니다. 어떤 사람들은 그것이 사실이라고 말하고 어떤 사람들은 그것이 거짓이라고 말하지만 합의는 없습니다. 또 다른 흥미로운 점은 솔루션이 RSA와 같은 공개 / 개인 키 암호화에 해로울 수 있다는 것입니다. RSA 키를 생성하는 것처럼 쉽게 중단 할 수 있습니다.

그리고 그것은 꽤 고무적인 문제입니다.

---

질문의 P =? NP 부분의 내용과 이유에 추가 할 수있는 것은 많지 않지만 증거와 관련하여 추가 할 수는 없습니다. 증거는 추가 크레딧의 가치가있을뿐만 아니라 밀레니엄 문제 중 하나를 해결할 것입니다 . 최근 흥미로운 여론 조사가 실시되었으며, 출판 된 결과 (PDF) 는 증거의 주제와 관련하여 읽을 가치가 있습니다.

---

먼저 일부 정의는 다음과 같습니다.

• 입력 크기가 어디에서 n^k일부 보다 적은 시간 내에 솔루션을 계산할 수있는 경우 특정 문제는 P에 있습니다 . 예를 들어, 보다 작은 정렬을 수행 할 수 있으므로 정렬은 다항식 시간입니다.knn log nn^2

• k기껏 n^k해야 제 시간에 확인할 수있는 크기의 솔루션 이 존재하는 경우 문제는 NP에 있습니다 n^k. 그래프의 3 색 표시 : 그래프에서 3 색은 크기가있는 (정점, 색) 쌍의 목록이며 모든 이웃이 다른 색을 가지고 있는지 O(n)시간 O(m)(또는 O(n^2))으로 확인할 수 있습니다 . 따라서 짧고 쉽게 확인할 수있는 솔루션이있는 경우에만 그래프를 3 색으로 표시 할 수 있습니다.

NP의 등가 정의 "문제는로 풀수 N 에 ondeterministic 튜링 기계 P olynomial 시간". 이름이 어디에서 왔는지 알려 주지만 NP 문제와 같은 직관적 인 느낌을주지는 않습니다.

P는 NP의 하위 집합입니다. 다항식 시간으로 솔루션을 찾을 수 있으면 다항식 시간으로 확인할 수있는 솔루션이 있습니다. 주어진 솔루션이 찾을 수있는 솔루션과 같은지 확인하십시오.

질문이 왜 P =? NP흥미로운가요? 이에 대한 답을 얻으려면 먼저 NP- 완전 문제가 무엇인지 알아야합니다. 간단히 말해서

• 문제 L은 (1) L이 P에 있고, (2) L을 해결하는 알고리즘을 사용하여 NP의 모든 문제 L '을 해결하는 경우 NP- 완료; 즉, L '의 인스턴스가 주어지면 L'의 인스턴스에 솔루션이있는 경우에만 솔루션이있는 L의 인스턴스를 작성할 수 있습니다. 공식적으로 말하면 NP의 모든 문제 L '은 L로 환원 됩니다.

L의 인스턴스는 다항식 시간 계산 가능해야하며 L '크기의 다항식 크기 ​​여야합니다. 그런 식으로 다항식 시간에 NP- 완전 문제를 해결하면 모든 NP 문제에 대한 다항식 시간 솔루션이 제공됩니다 .

예를 들면 다음과 같습니다. 그래프의 3 색 표시가 NP-hard 문제라는 것을 알고 있다고 가정합니다. 부울 공식의 만족도를 결정하는 것도 NP-hard 문제라는 것을 증명하고자합니다.

각 정점 v에 대해 두 개의 부울 변수 v_h 및 v_l과 요구 사항 (v_h 또는 v_l)이 있습니다. 각 쌍은 값 {01, 10, 11} 만 가질 수 있으며 이는 색상 1, 2 및 3으로 생각할 수 있습니다.

각 모서리 (u, v)에 대해 (u_h, u_l)! = (v_h, v_l) 요구 사항이 있습니다. 그건,

not ((u_h and not u_l) and (v_h and not v_l) or ...) 모든 동등한 구성을 열거하고 그 중 어느 것도 해당하지 않는 규정.

AND이 모든 제약 조건을 함께 사용하면 다항식 크기 ​​( O(n+m)) 를 갖는 부울 수식이 제공 됩니다. 계산하는 데 다항식 시간이 걸리는지 확인할 수 있습니다 O(1). 정점 및 모서리마다 간단한 작업을 수행하고 있습니다.

내가 만든 부울 공식을 풀 수 있다면 그래프 색상을 풀 수 있습니다. 각 변수 쌍 v_h와 v_l에 대해 v의 색을 해당 변수의 값과 일치하는 색으로 만듭니다. 수식을 구성하면 이웃의 색상이 동일하지 않습니다.

따라서, 그래프의 3 색이 NP- 완전이면, 부울-식-만족도입니다.

우리는 그래프의 3 색이 NP- 완전 함을 알고 있습니다. 그러나 역사적으로 우리는 먼저 부울 회로 만족도의 NP- 완전성을 보여준 다음 3 색으로 줄임으로써 (다른 방법으로)이를 알게되었습니다.

참고 URL : https://stackoverflow.com/questions/111307/whats-p-np-and-why-is-it-such-a-famous-question