P 대 NP 문제

새천년상 문제
버치와 스위너턴-다이어 추측 호지 추측 나비에 – 존재감과 부드러움을 강조합니다. P 대 NP 문제 푸앵카레 추측 (해결) 리만 가설 양-밀스의 존재와 질량 격차
v t

P 대 NP 문제는 이론 컴퓨터 과학에서 해결되지 않은 주요 문제입니다. 비공식적으로 솔루션을 신속하게 검증할 수 있는 모든 문제도 신속하게 해결할 수 있는지를 묻습니다.

여기서, 빠르게는 과제를 해결하고 다항 시간으로 실행되는 알고리즘이 존재함을 의미하며, 이는 알고리즘에 대한 입력의 크기(예를 들어, 지수 시간이 아닌)에 대한 다항 함수로서 과제 완료 시간이 변화함을 의미합니다. 어떤 알고리즘이 다항식 시간에 답할 수 있는 일반적인 질문 클래스는 "P" 또는 "클래스 P"입니다. 일부 질문의 경우 답변을 빠르게 찾을 수 있는 방법이 알려져 있지 않지만 답변이 제공되면 빠르게 검증할 수 있습니다. 다항식 시간에 답을 확인할 수 있는 질문의 클래스는 "비결정론적 다항식 시간"을 나타내는 NP입니다.^{[Note 1]}

P 대 NP 질문에 대한 답은 다항식 시간에 검증할 수 있는 문제도 다항식 시간에 해결할 수 있는지 여부를 결정합니다. 널리 알려진 P ≠ NP라면 NP에는 검증보다 계산하기 어려운 문제가 있다는 뜻입니다. 다항식 시간에는 풀 수 없었지만 다항식 시간에는 답을 검증할 수 있었습니다.

이 문제는 컴퓨터 과학에서 가장 중요한 미해결 문제로 불려왔습니다.^[1] 계산 이론에서 중요한 문제가 되는 것 외에도, 어느 쪽이든 증명은 수학, 암호학, 알고리즘 연구, 인공 지능, 게임 이론, 멀티미디어 처리, 철학, 경제학 및 기타 많은 분야에 깊은 영향을 미칠 것입니다.^[2]

Clay Mathematics Institute가 선정한 7개의 Millennium Prize Problems 중 하나이며, 각각의 문제는 첫 번째 정답에 대해 미화 1,000,000달러의 상금이 걸려 있습니다.

예

스도쿠 게임에서 플레이어는 부분적으로 채워진 숫자 그리드로 시작하여 게임의 규칙에 따라 그리드를 완성하려고 시도합니다. 불완전한 스도쿠 그리드를 감안할 때, 어떤 규모로든, 적어도 하나의 법적 해결책이 있습니까? 제안된 솔루션은 쉽게 검증되며 그리드가 커짐에 따라 솔루션을 확인하는 시간이 천천히(다항식적으로) 증가합니다. 그러나 솔루션을 찾기 위해 알려진 모든 알고리즘은 어려운 예를 들어 그리드가 커짐에 따라 기하급수적으로 증가하는 시간을 사용합니다. 따라서 수도쿠는 NP(빠른 확인 가능)에 있지만 P(빠른 해결 가능)에는 없는 것 같습니다. 수천 개의 다른 문제도 마찬가지로 확인하는 것은 빠르지만 해결하는 것은 느립니다. 연구자들은 NP의 많은 문제들이 NP의 다른 문제들에 대한 빠른 해결책을 구축하는 데 사용될 수 있는 추가적인 특성을 가지고 있다는 것을 보여주었는데, 이는 NP-완전성이라고 불리는 특성입니다. 수십 년 동안의 탐색은 이러한 문제들에 대한 빠른 해결책을 만들어내지 못했기 때문에, 대부분의 과학자들은 이러한 문제들이 빠르게 해결될 수 없다고 의심하지만, 이것은 증명되지 않았습니다.

역사

P 대 NP 문제의 정확한 진술은 1971년 스티븐 쿡에 의해 그의 중요한 논문 "정리 증명 절차의 복잡성"(^[3]그리고 1973년^[4] 레오니트 레빈에 의해 독립적으로)에서 소개되었습니다.

P 대 NP 문제는 1971년에 공식적으로 정의되었지만, 관련된 문제, 증명의 어려움 및 잠재적인 결과에 대한 이전의 인식이 있었습니다. 1955년 수학자 존 내시는 NSA에 편지를 보냈는데, 충분히 복잡한 코드를 해독하려면 키의 길이가 기하급수적인 시간이 필요할 것이라고 추측했습니다.^[5] 만약 (그리고 내쉬가 적절하게 회의적이었다는 것이 증명된다면) 이것은 제안된 키가 다항식 시간 내에 검증될 수 있기 때문에 현재 P ≠ NP라고 불리는 것을 의미할 것입니다. 근본적인 문제에 대한 또 다른 언급은 1956년 Kurt Gödel이 John von Neumann에게 쓴 편지에서 발생했습니다. 괴델은 정리 증명이 이차 시간 또는 선형 시간으로 해결될 수 있는지에 대해 물었고,^[6] 가장 중요한 결과 중 하나인 수학적 증명의 발견이 자동화될 수 있다고 지적했습니다.

맥락

복잡도 클래스 P와 NP 사이의 관계는 계산 복잡성 이론에서 연구되며, 계산 이론의 일부는 주어진 문제를 해결하기 위해 계산하는 동안 필요한 자원을 다룹니다. 가장 일반적인 리소스는 시간(문제를 해결하는 데 얼마나 많은 단계가 필요한지)과 공간(문제를 해결하는 데 얼마나 많은 메모리가 필요한지)입니다.

이러한 분석에서는 시간을 분석해야 하는 컴퓨터의 모델이 필요합니다. 일반적으로 이러한 모델은 컴퓨터가 결정론적이고(컴퓨터의 현재 상태와 입력을 고려할 때, 컴퓨터가 취할 수 있는 가능한 조치는 단 하나뿐이다) 순차적(작업을 차례로 수행한다)이라고 가정합니다.

이 이론에서 클래스 P는 입력 크기의 지속 시간 다항식에서 결정론적 순차 기계에서 풀 수 있는 모든 결정 문제(아래 정의)로 구성되며, 클래스 NP는 적절한 정보가 주어지면 다항식 시간 내에 양의 해를 확인할 수 있는 모든 결정 문제로 구성됩니다. determin이 아닌 기계에서 다항식 시간 내에 해를 구할 수 있습니다. 분명히, P ⊆ NP. 이론 컴퓨터 과학에서 가장 큰 미해결 문제는 이 두 부류 사이의 관계에 관한 것입니다.

P는 NP와 같습니까?

2002년부터 William Gasarch는 이것과 관련된 질문에 대해 연구자들을 대상으로 세 번의 여론조사를 실시했습니다.^[8][9][10] P ≠ NP가 증가하고 있다는 자신감 – 2019년에는 88%가 P ≠ NP를 믿었고, 2012년에는 83%, 2002년에는 61%였습니다. 전문가로 제한했을 때 2019년 답변은 99%가 P ≠ NP를 믿었습니다. 이러한 여론 조사는 P=NP 여부를 의미하지 않습니다. Gasarch 자신은 "이것이 P= 해결에 더 가까이 다가가지 못하게 합니까?NP 또는 언제 해결될지 알면서도 이 시대의 주관적인 의견에 대한 객관적인 보고서가 되려고 합니다."

NP-완전성

P = NP 질문을 공격하기 위해서는 NP-완전성의 개념이 매우 유용합니다. NP-완전 문제는 다른 NP 문제가 다항식 시간 내에 축소 가능하고 다항식 시간 내에 여전히 해결책을 확인할 수 있는 문제입니다. 즉, 임의의 NP 문제는 임의의 NP-완전 문제로 변환될 수 있습니다. 비공식적으로, NP-완전 문제는 적어도 NP의 다른 문제만큼 "힘든" NP 문제입니다.

NP-하드 문제는 적어도 NP 문제만큼 어려운 문제입니다. 즉, 모든 NP 문제를 (다항식 시간 내에) 그들로 줄일 수 있습니다. NP-하드 문제는 NP에 있을 필요가 없습니다. 즉, 다항식 시간에 검증 가능한 솔루션을 가질 필요가 없습니다.

예를 들어, 부울 만족도 문제는 Cook-Levin 정리에 의해 NP-완전이므로, NP에 있는 문제의 모든 인스턴스는 다항식 시간에 부울 만족도 문제로 기계적으로 변환될 수 있습니다. 부울 만족도 문제는 많은 NP-완전 문제 중 하나입니다. 만약 어떤 NP-완전 문제가 P에 있다면, 그 문제는 P = NP로 이어질 것입니다. 그러나 많은 중요한 문제는 NP-완전이며, 그 중 어느 것에 대한 빠른 알고리즘도 알려져 있지 않습니다.

정의만으로 NP-완전 문제가 존재한다는 것은 직관적이지 않습니다. 그러나 사소한 NP-완전 문제는 다음과 같이 공식화할 수 있습니다. 튜링 기계 M이 다항식 시간에 멈출 것을 보장한다면 M이 받아들일 다항식 크기의 입력이 존재합니까?^[11] 이것은 (입력이 주어지면) M을 시뮬레이션하여 M이 입력을 받아들였는지 확인하기 쉽기 때문에 NP에 있습니다. NP에 있는 문제의 특정 인스턴스에 대한 검증자는 솔루션을 입력으로 사용하는 다항식 시간 기계 M으로 인코딩될 수 있기 때문에 NP-완전합니다. 그런 다음 인스턴스가 yes인지 no instance인지의 문제는 유효한 입력이 존재하는지 여부에 따라 결정됩니다.

NP-완전성이 입증된 첫 번째 자연 문제는 SAT라고도 알려진 부울 만족도 문제였습니다. 위에서 언급한 바와 같이, 이것은 쿡-레빈 정리이며, 만족도가 NP-완전이라는 증명은 NP의 정의와 관련된 튜링 기계에 대한 기술적 세부 사항을 포함합니다. 그러나 이 문제가 NP-완전임이 입증된 후 축소에 의한 증명은 앞서 논의한 스도쿠 게임을 포함하여 다른 많은 문제도 NP-완전임을 보여주는 더 간단한 방법을 제공했습니다. 이 경우 증명은 다항식 시간에 스도쿠 해를 사용하여 다항식 시간에 라틴 제곱을 완성할 수도 있음을 보여줍니다.^[12] 이는 삼자 그래프를 삼각형으로 분할하는 문제에 대한 해결책을 제공하며,^[13] 이는 3-SAT로 알려진 특수한 경우의 해결책을 찾는 데 사용될 수 있으며,^[14] 이는 일반적인 부울 만족도에 대한 해결책을 제공합니다. 따라서 스도쿠에 대한 다항식 시간 솔루션은 일련의 기계적 변환을 통해 만족도의 다항식 시간 솔루션으로 이어지며, 이는 다항식 시간에서 다른 NP 문제를 해결하는 데 사용될 수 있습니다. 이와 같은 변환을 사용하면 관련이 없어 보이는 방대한 종류의 문제가 서로 축소될 수 있으며, 어떤 의미에서는 "같은 문제"가 됩니다.

더 어려운 문제들

P = NP인지는 알 수 없지만 P 이외의 문제는 알려져 있습니다. 클래스 P가 다항식 실행 시간으로 정의되는 것처럼 클래스 EXPTIME은 지수 실행 시간을 갖는 모든 의사 결정 문제의 집합입니다. 즉, EXPTIME의 모든 문제는 결정론적 튜링 기계에 의해 O(2^p(n)) 시간에 해결될 수 있으며, 여기서 p(n)은 n의 다항 함수입니다. 결정 문제가 EXPTIME에 있으면 EXPTIME은 완전하며, EXPTIME의 모든 문제는 그것에 대한 다항식 시간의 다중 원 감소를 갖습니다. 많은 문제들이 EXPTIME-완전한 것으로 알려져 있습니다. P가 EXPTIME을 ≠한다는 것을 알 수 있기 때문에 이러한 문제는 P 외부에 있으므로 다항식 이상의 시간이 필요합니다. 사실, 시간 계층 정리에 의해, 그것들은 지수 시간보다 훨씬 적은 시간에 해결될 수 없습니다. 예를 들어 N × N 보드의^[15] 체스 위치에 대한 완벽한 전략과 다른 보드 게임에 대한 유사한 문제를 찾는 것이 포함됩니다.^[16]

프레스버거 산술에서 진술의 진실을 결정하는 문제는 훨씬 더 많은 시간을 필요로 합니다. 피셔와 라빈은 1974년^[17] 길이 n의 프레스버거 문장의 참값을 결정하는 모든 알고리즘이 어떤 상수 c에 대해$$ 적어도 ${\displaystyle {22{\mathrm{}}^{}}^{}}$ ${\displaystyle {{\mathrm{cn}}^{}}^{}}$ ${\$의 런타임을 갖는다는 것을 증명했습니다. 따라서 이 문제는 기하급수적인 실행 시간 이상이 필요한 것으로 알려져 있습니다. 더 어려운 것은 정지 문제와 같은 결정되지 않은 문제입니다. 어떤 특정 알고리즘에 대해서도 그 알고리즘이 정답을 만들지 못하는 입력이 적어도 하나 존재한다는 점에서, 그 알고리즘은 완벽하게 해결할 수 없습니다; 그것은 오답을 생성하거나, 결정적인 답을 주지 않고 끝나거나, 그렇지 않으면 전혀 답을 생성하지 않고 영원히 실행될 것입니다.

결정 문제 이외의 질문도 고려할 수 있습니다. 계산 문제로 구성된 이러한 클래스 중 하나를 #P라고 합니다. NP 문제가 "해가 있습니까?"라고 묻는다면, 해당 #P 문제는 "해가 몇 개 있습니까?"라고 묻습니다. 분명히 #P 문제는 적어도 하나의 해가 존재하는지, 만약 그 해가 0보다 크면 즉시 알려주기 때문에 적어도 해당 NP 문제만큼은 어려울 것입니다. 놀랍게도 어렵다고 여겨지는 일부 #P 문제는 쉬운(예: 선형 시간) P 문제에 해당합니다.^[18] 이러한 문제의 경우 솔루션이 존재하는지 여부를 구분하는 것은 매우 쉽지만 몇 개인지를 구분하는 것은 매우 어렵다고 생각됩니다. 이러한 문제들 중 많은 것들은 #P-완전이며, 따라서 #P에서 가장 어려운 문제들 중 하나입니다. 왜냐하면 그들 중 어느 것에 대한 다항식 시간 해는 다른 모든 #P 문제에 대한 다항식 시간 해를 허용하기 때문입니다.

P 또는 NP-완전이 아닌 NP의 문제

1975년에 Richard E. Ladner는 P가 NP에 ≠를 하면 NP에는 P도 NP-완전도 아닌 문제가 존재한다는 것을 보여주었습니다. 이러한 문제를 NP-중간 문제라고 합니다. 그래프 동형 문제, 이산 로그 문제, 정수 인수분해 문제는 NP-중간으로 추정되는 문제의 예입니다. 그들은 P에 없거나 NP-완전한 것으로 알려져 있지 않은 극소수의 NP 문제 중 일부입니다.

그래프 동형 문제는 두 개의 유한 그래프가 동형인지 여부를 결정하는 계산 문제입니다. 복잡도 이론에서 중요한 미해결 문제는 그래프 동형화 문제가 P, NP-완전 또는 NP-중간에 있는지 여부입니다. 답은 알려지지 않았지만 문제는 적어도 NP-완전이 아니라고 생각됩니다.^[20] 그래프 동형화가 NP-완전인 경우 다항식 시간 계층 구조가 두 번째 수준으로 붕괴됩니다.^[21] 다항식 계층 구조는 어떤 유한 수준으로도 붕괴되지 않는다고 널리 알려져 있기 때문에 그래프 동형화가 NP-완전하지 않다고 생각됩니다. László Babai로 인해 이 문제에 대한 최적의 알고리즘은 준다항식 시간에 실행됩니다.^[22]

정수 인수분해 문제는 주어진 정수의 소인수분해를 결정하는 계산 문제입니다. 결정 문제로 표현하면 입력이 k보다 작은 인자를 갖는지 여부를 결정하는 문제입니다. 효율적인 정수 인수분해 알고리즘은 알려져 있지 않으며, 이 사실은 RSA 알고리즘과 같은 여러 현대 암호 시스템의 기초를 형성합니다. 정수 인수분해 문제는 NP와 co-NP(심지어 UP과 co-UP^[23])에 있습니다. 문제가 NP-완전인 경우 다항식 시간 계층 구조는 첫 번째 수준(즉, NP = co-NP)으로 붕괴됩니다. 정수 인수분해를 위한 가장 효율적인 알려진 알고리즘은 예상 시간이 걸리는 일반적인 수 필드 체입니다.

${\displaystyle O\left(\exp \left({\tfrac {64n}{9}\log(2)\right)^{\frac {1}{3}\left(\log(n\log(2)\right)^{\frac {2}{3}\right)}$

n-비트 정수를 인수분해합니다. 이 문제에 대해 가장 잘 알려진 양자 알고리즘인 쇼의 알고리즘은 다항식 시간에 실행되지만, 이것이 문제가 양자가 아닌 복잡성 클래스와 관련하여 어디에 있는지를 나타내는 것은 아닙니다.

P는 "쉽다"는 뜻입니까?

위의 모든 논의는 P가 "쉽다"는 뜻이고, P에 있지 않다가 "어렵다"는 뜻이라고 가정하였는데, 이는 코밤의 논문으로 알려진 가정입니다. 복잡성 이론에서 일반적이고 합리적으로 정확한^{[citation needed]} 가정이지만 주의해야 할 사항이 있습니다.

첫째, 실제로는 거짓일 수 있습니다. 이론 다항식 알고리즘은 상수 인자나 지수가 매우 커서 비현실적일 수 있습니다. 예를 들어, 그래프 G가 H를 마이너로 포함하는지 여부를 결정하는 문제는 O(n²)의 실행 시간에 해결할 수 있으며,^[25] 여기서 n은 G의 정점 수이다. 그러나 큰 O 표기법은 초지수적으로 H에 의존하는 상수를 숨깁니다. 상수는 $2$ ↑↑ ${\displaystyle (2}$ ↑↑${\displaystyle }$(${\displaystyle 2}$ ↑↑${\displaystyle }$(${\displaystyle h}$/ ${\displaystyle 2\uparrow \uparrow (2\uparrow \uparrow$ ($2\uparrow \uparrow (h/2))}($Knuth의 상위 arrow 표기법 사용)보다 크며, 여기서 h는 H의 정점 수이다.

반면에 문제가 NP-완전한 것으로 나타나더라도, 그리고 P가 NP에 ≠하더라도, 실제로 문제에 대한 효과적인 접근법은 여전히 존재할 수 있습니다. 배낭 문제, 여행 세일즈맨 문제, 부울 만족도 문제와 같은 많은 NP-완전 문제에 대한 알고리즘이 있으며, 이는 많은 실제 인스턴스를 합리적인 시간에 최적화할 수 있습니다. 이러한 알고리즘의 경험적 평균 사례 복잡성(시간 대 문제 크기)은 놀라울 정도로 낮을 수 있습니다. 그 예로 선형 프로그래밍의 심플렉스 알고리즘이 있는데, 실제로는 놀라울 정도로 잘 작동합니다. 기하급수적인 최악의 경우 시간 복잡성을 가지고 있음에도 불구하고 가장 잘 알려진 다항식 시간 알고리즘과 동등하게 작동합니다.^[27]

마지막으로 양자 계산, 무작위 알고리즘 등 P와 NP가 정의된 튜링 머신 모델에 부합하지 않는 계산 유형이 있습니다.

P ≠ NP 또는 P = NP라고 믿는 이유

Cook은 P 대 NP 문제의 문제를 "P = NP입니까?"로 다시 설명합니다. 여론조사에 따르면 대부분의 컴퓨터 과학자들은 P가 NP를 ≠한다고 믿고 있습니다. 이 믿음의 핵심적인 이유는 수십 년 동안 이 문제들을 연구한 결과 아무도 알려진 3000개 이상의 중요한 NP-완전 문제에 대한 다항 시간 알고리즘을 찾을 수 없었기 때문입니다(NP-완전 문제 목록 참조). 이 알고리즘들은 NP-완전성의 개념이 정의되기도 전에 모색되었습니다(처음 발견된 것 중 Karp의 21개 NP-완전 문제는 모두 NP-완전성으로 나타났던 당시 잘 알려진 기존 문제였습니다). 또한, 결과 P = NP는 NP = co-NP 및 P = PH와 같이 현재 거짓이라고 여겨지는 많은 놀라운 결과를 의미합니다.

또한 해결하기 어렵지만 검증하기 쉬운 문제의 존재가 실제 경험과 일치한다고 직관적으로 주장합니다.^[30]

만약 P = NP라면, 세상은 우리가 보통 가정하는 것과는 완전히 다른 곳이 될 것입니다. "창의적 도약"에는 특별한 가치가 없을 것이며, 문제를 해결하는 것과 해결책을 인식하는 것 사이에 근본적인 격차가 없을 것입니다.

— Scott Aaronson, UT Austin

반면, 일부 연구자들은 P ≠ NP를 믿는 것에 대한 과신이 있으며, 연구자들이 P = NP의 증명도 함께 탐구해야 한다고 믿고 있습니다. 예를 들어, 2002년에 이러한 진술이 이루어졌습니다.^[8]

P ≠ NP를 찬성하는 주요 주장은 철저한 탐색 영역에서 근본적인 진전이 전혀 없다는 것입니다. 이것은 제가 보기에는 굉장히 약한 주장입니다. 알고리즘의 공간은 매우 넓고 우리는 이제 겨우 탐구의 시작에 있습니다. 페르마의 마지막 정리의 해결도 매우 간단한 문제들이 매우 깊은 이론들에 의해서만 해결될 수 있다는 것을 보여줍니다.

— Moshe Y. Vardi, Rice University

추측에 집착하는 것은 연구 계획에 대한 좋은 지침이 아닙니다. 모든 문제에 대해 항상 양방향으로 시도해야 합니다. 편견은 유명한 수학자들이 필요한 모든 방법을 개발했음에도 불구하고 그들의 예상과 반대로 풀이되는 유명한 문제를 푸는 데 실패하게 만들었습니다.

— Anil Nerode, Cornell University

DLIN vs NLIN

P와 NP의 정의에서 "다중 테이프 튜링 기계의 선형 시간"을 "다항식 시간"으로 대체하면 DLIN과 NLIN 클래스를 얻습니다. DLIN ≠ NLIN이라고 알려져 있습니다.

솔루션의 결과

이 문제가 그렇게 많은 관심을 끄는 이유 중 하나는 가능한 답변의 결과입니다. 어느 쪽의 해결 방향도 이론을 엄청나게 발전시킬 것이고, 아마도 거대한 실질적인 결과를 가져올 것입니다.

P = NP

P = NP가 NP의 중요한 문제들 중 일부를 해결하는 효율적인 방법으로 이어진다면 놀라운 실용적인 결과를 가져올 수 있다는 증거입니다. 다양한 NP-완전 문제가 많은 분야에서 기본이기 때문에 긍정적인 결과와 부정적인 결과가 모두 발생합니다.

증명이 NP-완전 문제에 대한 실제 알고리즘으로 이어지지 않을 가능성도 매우 높습니다. 문제의 공식화는 경계 다항식이 작거나 심지어 특별히 알려져 있을 필요가 없습니다. 비건설적인 증명은 해를 얻을 알고리즘이나 특정 경계를 지정하지 않고 해가 존재한다는 것을 보여줄 수 있습니다. 증명이 건설적이고 명시적인 경계 다항식 및 알고리즘 세부 사항을 보여주더라도 다항식이 매우 낮은 차수가 아니라면 알고리즘이 실제로 충분히 효율적이지 않을 수 있습니다. 이 경우 초기 증명은 주로 이론가들에게 흥미로울 것이지만 다항식 시간 솔루션이 가능하다는 지식은 확실히 이를 달성하기 위한 더 나은(그리고 아마도 실용적인) 방법에 대한 연구에 박차를 가할 것입니다.

P = NP를 보여주는 솔루션은 특정 문제가 어렵기 때문에 의존하는 암호화 분야를 뒤집을 수 있습니다. 3-SAT와 같은 NP-완전 문제에 대한 건설적이고 효율적인 해결책은^{[Note 2]} 다음과 같은 대부분의 기존 암호 시스템을 깨뜨릴 것입니다.

• 인터넷을 통한 안전한 금융 거래와 같은 많은 최신 보안 애플리케이션의 기반인 ^[32]공개 키 암호화의 기존 구현.
• 통신 데이터의 암호화에 사용되는 ^[33]AES 또는 3DES와 같은 대칭 암호입니다.
• 암호 해싱은 비트코인과 같은 블록체인 암호화폐의 기초가 되며 소프트웨어 업데이트를 인증하는 데 사용됩니다. 이러한 애플리케이션의 경우 주어진 값에 해쉬하는 사전 이미지를 찾는 것은 매우 어려우며 기하급수적인 시간이 소요되는 것이 이상적입니다. P = NP인 경우 SAT로 축소를 통해 다항식 시간이 소요될 수 있습니다.

P ≠ NP를 가정하지 않는 정보 이론적으로 안전한 솔루션으로 수정 또는 교체해야 합니다.

또한 현재 수학적으로 다루기 힘든 많은 문제를 다루기 쉽게 만드는 것으로 인해 얻을 수 있는 엄청난 이점이 있습니다. 예를 들어, 정수 프로그래밍 유형 및 출장 세일즈맨 문제와 같은 운영 연구의 많은 문제는 NP-완전입니다. 이러한 문제에 대한 효율적인 해결책은 물류에 막대한 영향을 미칠 것입니다. 단백질 구조 예측의 일부 문제와 같은 다른 많은 중요한 문제들도 NP-완전합니다.^[35] 이러한 문제들을 효율적으로 해결할 수 있도록 하는 것은 생명과학과 생명공학을 상당히 발전시킬 수 있습니다.

이러한 변화는 수학 자체에서 NP-완전 문제를 효율적으로 해결하는 혁명에 비해 미미할 수 있습니다. 괴델은 계산 복잡도에 대한 초기 생각에서 어떤 문제라도 해결할 수 있는 기계적 방법이 수학에 혁명을 일으킬 것이라고 언급했습니다.^[36][37]

φ(n) ~ k ⋅n(또는 심지어 ~ k ⋅n)을 갖는 기계가 실제로 존재한다면, 이는 가장 중요한 결과를 초래할 것입니다. 즉, 엔체이둥 문제의 결정 불가능성에도 불구하고 예 또는 아니오 문제에 관한 수학자의 정신적 작업이 기계로 완전히 대체될 수 있음을 분명히 의미합니다. 결국, 기계가 결과를 제공하지 않을 때 문제에 대해 더 생각하는 것은 말이 되지 않을 정도로 큰 자연수 n을 선택하면 됩니다.

마찬가지로 스티븐 쿡(Stephen Cook)은 증명뿐만 아니라 실질적으로 효율적인 알고리즘을 가정하여 다음과 같이 말합니다.^[28]

... 형식적 증명은 다항식 시간에 쉽게 인식될 수 있기 때문에, 컴퓨터가 적당한 길이의 증명을 갖는 어떤 정리에 대한 형식적 증명을 찾도록 함으로써 수학을 변형시킬 것입니다. 예시적인 문제에는 CMI 상 문제가 모두 포함될 수 있습니다.

연구 수학자들은 정리를 증명하는 데 경력을 쏟는데, 어떤 증명은 문제가 밝혀진 후에 찾는 데 수십 년, 심지어 몇 세기가 걸렸습니다. 예를 들어, 페르마의 마지막 정리는 증명하는 데 3세기가 넘게 걸렸습니다. "합리적인" 크기 증명이 존재한다면 증명을 찾도록 보장되는 방법은 본질적으로 이 투쟁을 끝낼 것입니다.

Donald Knuth는 P = NP를 믿게 되었다고 말했지만, 가능한 증거의 영향에 대해서는 유보적입니다.

[...] "무한성을 가진 coping"에 관한 논문에서 설명한 숫자 10↑↑↑↑3처럼 유한하지만 엄청나게 큰 숫자 M을 상상한다면, n개의 주어진 비트에서 비트 단위 또는 덧셈 또는 시프트 연산을 수행하는 수많은 가능한 알고리즘이 존재하며, 이 모든 알고리즘이 실패한다고 믿기는 정말 어렵습니다. 그러나 내 요점은, 그런 증명은 거의 확실히 비건설적일 것이기 때문에, 동등성 P = NP가 증명되더라도 도움이 되지 않을 것이라고 생각하지 않는다는 것입니다.

P ≠ NP

P ≠ NP에 대한 증명은 P = NP라는 증명의 실질적인 계산상 이점이 부족하지만, 계산 복잡도 이론의 큰 발전을 나타내며 향후 연구를 안내할 수 있습니다. 이는 많은 일반적인 문제를 효율적으로 해결할 수 없음을 보여줌으로써 연구자의 관심이 부분적인 해결책이나 다른 문제에 대한 해결책에 집중될 수 있음을 보여줍니다. P ≠ NP에 대한 광범위한 믿음으로 인해 이러한 연구 집중은 이미 많이 이루어졌습니다.

P ≠ NP는 여전히 NP에서 하드 문제의 평균-경우 복잡성을 열어줍니다. 예를 들어, 최악의 경우 SAT는 지수 시간이 필요하지만 무작위로 선택된 거의 모든 인스턴스를 효율적으로 해결할 수 있습니다. Russell Impaglizo는 평균 사례의 복잡성 문제에 대한 해결 방법이 다르기 때문에 발생할 수 있는 다섯 가지 가상의 "세계"에 대해 설명했습니다.^[40] P = NP 및 SAT와 같은 문제를 모든 경우에 효율적으로 해결할 수 있는 "알고리즘"부터 P ≠ NP 및 P 외부의 문제의 하드 인스턴스 생성이 용이한 "크립토마니아"에 이르기까지 세 가지 중간 가능성은 NP-하드 문제의 인스턴스에 대한 상이한 난이도 분포를 반영합니다. P ≠ NP이지만 NP의 모든 문제가 평균적인 경우에 다루기 쉬운 "세계"를 논문에서는 "Heurista"라고 부릅니다. 2009년 프린스턴 대학 워크숍에서 다섯 세계의 현황을 연구했습니다.^[41]

증명 난이도에 대한 결과

백만 달러의 상금과 엄청난 양의 헌신적인 연구에도 불구하고 P = NP 문제 자체는 여전히 열려 있지만, 문제를 해결하기 위한 노력은 몇 가지 새로운 기술로 이어졌습니다. 특히 P = NP 문제와 관련된 가장 효과적인 연구 중 일부는 기존 증명 기법이 질문에 답하기에 불충분하다는 것을 보여줌으로써 새로운 기술적 접근이 필요함을 시사했습니다.

문제의 난이도에 대한 추가적인 증거로, 계산 복잡도 이론에서 기본적으로 알려진 모든 증명 기법은 다음 분류 중 하나에 속하며, 모두 P ≠ NP를 증명하기에는 불충분합니다.

분류	정의.
증명 상대화	모든 알고리즘이 오라클이라는 고정된 서브루틴에 쿼리를 할 수 있고(예를 들어, 여행 중인 판매원 문제를 한 번에 해결하는 오라클과 같이 고정된 일련의 질문에 일정한 시간 내에 답할 수 있다), 오라클의 실행 시간은 알고리즘의 실행 시간에 비해 계산되지 않는 세상을 상상해 보세요. 대부분의 증명(특히 고전적 증명)은 오라클이 있는 세계에서 오라클이 하는 일에 관계없이 균일하게 적용됩니다. 이러한 증명을 상대화라고 합니다. 1975년 베이커, 길, 솔로베이는 일부 오라클에 대해 P = NP인 반면 다른 오라클에 대해서는 P ≠ NP임을 보여주었습니다. 상대화 증명은 가능한 모든 오라클에 대해 참인 문장만 증명할 수 있으므로 이러한 기법으로는 P = NP를 해결할 수 없습니다.
자연 증명	1993년 알렉산더 라즈보로프와 스티븐 루디치는 회로 복잡도 하한에 대한 일반적인 종류의 증명 기법을 정의했는데, 이를 자연 증명이라고 합니다.[43] 그 당시에는 이전에 알려진 모든 회로 하한선이 자연스러웠고 회로 복잡성은 P = NP를 해결하는 데 매우 유망한 접근법으로 간주되었습니다. 그러나 라즈보로프와 루디치는 단방향 함수가 존재한다면 P와 NP는 자연 증명 방법과 구별할 수 없음을 보여주었습니다. 단방향 함수의 존재는 증명되지 않았지만, 대부분의 수학자들은 단방향 함수가 존재한다고 믿고 있으며, 그들의 존재에 대한 증명은 P ≠ NP보다 훨씬 더 강력한 진술이 될 것입니다. 따라서 자연 증명만으로는 P = NP를 해결할 수 없을 것 같습니다.
증명의 대수화	Baker-Gill-Solovay 결과가 나온 후, 새로운 relat을 유발하지 않는 증명 기법을 사용하여 IP = PSPACE를 성공적으로 증명했습니다. 그러나 2008년 Scott Aaronson과 Avi Wigderson은 산술화로 알려진 IP = PSPACE 증명에 사용된 주요 기술 도구도 P = NP를 해결하는 데 충분하지 않다는 것을 보여주었습니다. 산술화는 알고리즘의 연산을 대수적이고 기본적인 산술 기호로 변환한 다음 이를 사용하여 연산을 분석합니다. IP = PSPACE 증명에서는 블랙박스와 부울 회로를 대수적 문제로 변환합니다. 앞서 언급했듯이 이 방법은 P = NP 및 기타 시간 복잡성 문제를 해결하는 데 적합하지 않다는 것이 입증되었습니다.

이러한 장벽은 NP-완전 문제가 유용한 또 다른 이유입니다. 만약 다항 시간 알고리즘이 NP-완전 문제에 대해 입증될 수 있다면, 이것은 위의 결과에 의해 배제되지 않는 방식으로 P = NP 문제를 해결할 것입니다.

이러한 장벽으로 인해 일부 컴퓨터 과학자들은 P 대 NP 문제가 ZFC와 같은 표준 공리 시스템과 독립적일 수 있다고 제안합니다(그들 내에서 증명하거나 반증할 수 없음). 독립성 결과는 P ≠ NP와 이것이 (예를 들어) ZFC에서 증명할 수 없거나 P = NP이지만 어떤 다항식 시간 알고리즘도 정확하다는 것을 ZFC에서 증명할 수 없다는 것을 의미할 수 있습니다. 그러나 정수 산술에 대한 페아노 공리를 확장하는 훨씬 약한 가정에서도 문제를 결정할 수 없는 경우 모든 NP 문제에 대해 거의 다항식 시간 알고리즘이 존재합니다.^[46] 따라서 (대부분의 복잡성 이론가들이 그렇듯이) 일부 NP 문제에 효율적인 알고리즘이 없다고 가정하면 이러한 기술로 독립성을 증명하는 것은 불가능합니다. 이는 또한 현재 기술로 PA 또는 ZFC로부터의 독립성을 증명하는 것이 모든 NP 문제가 효율적인 알고리즘을 가지고 있음을 증명하는 것보다 쉽지 않음을 의미합니다.

논리적 특성화

P = NP 문제는 설명적 복잡성에서 작업한 결과 특정 클래스의 논리 진술로 재작성될 수 있습니다.

선형 순서 관계를 포함하여 부호가 고정된 유한 구조의 모든 언어를 고려합니다. 그런 다음 P의 모든 언어는 적합한 최소 고정 소수점 조합기를 추가하여 1차 논리로 표현할 수 있습니다. 재귀 함수는 이것과 차수 관계로 정의할 수 있습니다. 서명이 구별되는 순서 관계에 더하여 적어도 하나의 술어 또는 함수를 포함하고, 따라서 그러한 유한 구조를 저장하기 위해 취해진 공간의 양이 실제로 구조 내의 요소 수에서 다항식인 한, 이것은 정확하게 P를 특징짓습니다.

마찬가지로 NP는 존재론적인 2차 논리로 표현할 수 있는 언어 집합, 즉 관계, 함수 및 부분 집합에 대한 보편적인 정량화를 배제하도록 제한된 2차 논리입니다. 다항식 계층 구조의 언어 PH는 모든 2차 논리에 해당합니다. 따라서 "P가 NP의 적절한 부분 집합인가?"라는 질문은 "존재적인 2차 논리가 최소한의 고정점을 가진 1차 논리가 설명할 수 없는 (사소한 서명을 가진 유한한 선형 순서 구조의) 언어를 설명할 수 있는가?"^[47]로 재구성될 수 있습니다. P = PH인 경우에만 P = NP (전자와 같이 NP = co-NP가 성립하고 NP = PH인 경우)라는 단어는 이전의 특성에서 삭제될 수도 있습니다.

다항 시간 알고리즘

NP-완전 문제에 대한 알려진 알고리즘이 다항식 시간에 실행되지 않습니다. 그러나 P = NP인 경우 알고리즘이 인스턴스를 수락할 때 다항식 시간으로 실행되는 NP-완전 문제에 대해 알려진 알고리즘이 있습니다(비록 엄청난 상수가 있으므로 알고리즘이 비현실적입니다). 그러나 이러한 알고리즘은 인스턴스를 거부할 때의 실행 시간이 다항식이 아니기 때문에 다항식 시간으로 간주되지 않습니다. Levin(인용 없이)에 의한 다음 알고리즘은 아래와 같은 예입니다. NP-완전 언어 서브셋-SUM을 올바르게 받아들입니다. P = NP인 경우에만 서브셋-SUM에 있는 입력에서 다항식 시간으로 실행됩니다.

// NP-완전 언어 서브셋-SUM을 받아들이는 알고리즘 // // 이것은 P = NP인 경우에만 다항식 시간 알고리즘입니다. // // "다항식 시간"은 // 답이 "예"여야 할 때 다항식 시간에 "예"를 반환하고 "아니오"일 때 영원히 실행됩니다. //// 입력: S = 정수의 유한 집합 // 출력: S의 임의의 부분 집합이 0. // 출력 없이 영원히 실행됩니다. // 참고: "프로그램 번호 M"은 정수 M을 이진법으로 작성한 후 // 비트열을 // 프로그램으로 간주하여 얻은 프로그램입니다. 가능한 모든 프로그램은 // 이러한 방식으로 생성될 수 있지만 대부분은 구문 오류로 인해 //을(를) 수행하지 않습니다. FOR K = 1...∞   FOR M = 1...입력 S를 사용하여 K 단계의 프로그램 번호 M을 실행합니다. 프로그램이 고유한 정수 목록을 출력하고 정수가 모두 S이고 정수 합이 0인 경우 "예" 및 "정지"를 출력합니다. 

이것은 P = NP인 경우에만 NP-완전 언어를 허용하는 다항식 시간 알고리즘입니다. "수용"은 다항식 시간에 "예"라는 대답을 제공하지만, 대답이 "아니오"일 때(반 algorithm라고도 함) 영원히 실행되도록 허용된다는 것을 의미합니다.

이 알고리즘은 P = NP일지라도 엄청나게 비현실적입니다. 다항 시간에 서브셋-SUM을 풀 수 있는 가장 짧은 프로그램이 b비트라면, 위 알고리즘은 적어도 2 - 1개의 다른 프로그램을 먼저 시도할 것입니다.

형식적 정의

P와 NP

결정 문제는 알파벳 σ 위의 일부 문자열을 입력으로 받아 "예" 또는 "아니오"를 출력하는 문제입니다. 최대 cn^k 단계에서 길이가 n인 입력 문자열에 대한 정답을 생성하는 알고리즘(예를 들어 튜링 머신 또는 무한 메모리가 있는 컴퓨터 프로그램)이 있다면, k와 c는 입력 문자열에 독립적인 상수이며, 다항 시간 내에 문제가 해결될 수 있다고 말하고 클래스 P에 배치합니다. 형식적으로 P는 결정론적 다항 시간 튜링 기계에 의해 결정될 수 있는 언어 집합입니다. 의미.

${\displaystyle \mathbf {P} =\{L:어떤 결정론적 다항 시간 튜링 기계에 대한 L=L(M){\text{}}M\}$

어디에

${\displaystyle L(M)=\{w\in \Sigma ^{*:M{\text{수용}}w\}$

결정론적 다항 시간 튜링 기계는 다음 두 가지 조건을 만족하는 결정론적 튜링 기계 M입니다.

1. 모든 입력 워드에서 중지
2. ${\displaystyle {TM}^{}({}^{})}$∈ O$(nk$) ${\displaystyle T_{$M}(n$)\backslash$in O(n^{k})}가 되도록 $k$ ∈ N ${\displaystyle$k\in N}이(가) 존재하며, 여기서 O는 큰 O 표기법과

${\displaystyle T_{M}(n)=\max\{t_{M}(w):w\in \Sigma ^{*}, w =n\}}$

${\displaystyle t_{M}(w)={\text{단계 수}}M{\text{입력 시 중지됨}w.}$

NP는 비결정론적 튜링 머신(전통적인 방식)을 사용하여 유사하게 정의할 수 있습니다. 그러나 현대적인 접근 방식은 인증서와 검증자의 개념을 사용합니다. 형식적으로 NP는 다항식 시간에 실행되는 유한한 알파벳과 검증자를 가진 언어 집합입니다. 다음은 "검증자"를 정의합니다.

L을 유한 알파벳 σ 위의 언어로 가정해 보겠습니다.

L ∈ NP는 이진${\displaystyle {}^{}}$ ${\displaystyle {}^{}}$⊂ ∗$$× σ ∗ {\displaystyle R\subset \Sigma ^{*}\times \Sigma ^{*} 및 다음 두 조건이 만족되도록 양의 정수 k가 있는 경우에만 σ됩니다.

1. For all ${\displaystyle x\in \Sigma ^{*}}$, ${\displaystyle x\in L\Leftrightarrow \exists y\in \Sigma ^{*}}$ such that (x, y) ∈ R and ${\displaystyle y \in O( x ^{k})}$; and
2. 언어는 결정론적 튜링 기계에 의해 다항 시간 내에 결정됩니다.

L을 결정하는 튜링 기계를 L에 대한 검증기라고 하며, (x, y) ∈ R을 L에 대한 x의 소속 증명서라고 합니다.

모든 검증자가 다항식 시간일 필요는 없습니다. 그러나 L이 NP에 있으려면 다항식 시간에 실행되는 검증자가 있어야 합니다.

예

허락하다

${\displaystyle \mathrm {COMPOSITE} =\left\{x\in \mathbb {N} \mid x=pq{\text{(정수의 경우)}p,q>1\right\}}$

${\displaystyle R=\left\{(x,y)\in \mathbb {N} \times \mathbb {N} \mid 1<y\leq {\sqrt {x}} {\text{ and }}y{\text{dives }x\right\}}$

x의 값이 복합재인지 여부는 x가 복합재의 구성원인지 여부와 동일합니다. 위의 정의를 만족하는지 확인함으로써 합성 ∈ NP가 있음을 알 수 있습니다(이진 표현으로 자연수를 식별하면).

COMPOSITE 또한 P에 있으며, 이는 AKS primality test의 발명에 의해 입증된 사실입니다.^[48]

NP-완전성

NP-완전성을 설명하는 여러 가지 동등한 방법이 있습니다.

L을 유한 알파벳 σ 위의 언어로 가정해 보겠습니다.

L은 다음 두 조건을 만족하는 경우에만 NP-완전입니다.

1. L ∈ NP; 및
2. NP의 임의의 L'은 $다음{\displaystyle {}^{}}$ 두 조건을 만족하는 경우에만$$ L${\displaystyle {\text{'}}^{}}$ ${\displaystyle \le {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle L'\leq$ $_$${p}L}$로 표기되며,$$ 여기서 $L{\displaystyle {}^{\text{'}}}$ ${\displaystyle \le {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle L'\leq$ _${p}L}$로 표기됩니다.
   1. f: σ* → σ*이 존재하므로 모든 ${\displaystyle \mathrm{win}}$σ*에 대해${\displaystyle \mathrm{다음}}$과 같습니다. ${\displaystyle (}$w$$∈ L'$$⇔ f (w ) ∈ L) $\{\backslash$displaystyle (w\in L'\left right arrow f (w)\in L)}; 및
   2. 임의의 입력 w의 테이프에서 f(w)로 중단되는 다항 시간 튜링 기계가 존재합니다.

또는 L이 NP를 ∈하고 다항식 시간을 L로 줄일 수 있는 또 다른 NP-완전 문제가 있으면 L은 NP-완전입니다. 이것은 일부 새로운 문제가 NP-완전임을 증명하는 일반적인 방법입니다.

청구솔루션

P 대 NP 문제는 일반적으로 해결되지 않은 것으로 간주되지만 ^[49]많은 아마추어와 일부 전문 연구원은 해결책을 주장했습니다. 게르하르트 J. Woginger는 1986년부터 2016년까지 62개의 P = NP 증명으로 추정되는 목록을 작성했는데, 그 중 50개는 P ≠ NP의 증명이었고, 2개는 문제가 증명할 수 없는 증명이었고, 1개는 결정할 수 없는 증명이었습니다. P 대 NP를 해결하려는 일부 시도는 언론의 주목을 받았지만 이러한 시도는 반박되었습니다.^[51]

대중문화

티모시 랜존 감독의 영화 '여행 세일즈맨'은 P 대 NP 문제를 풀기 위해 미국 정부에 의해 고용된 네 명의 수학자들의 이야기입니다.^[52]

심슨 가족의 일곱 번째 시즌 "Treehouse of Horror VI"의 여섯 번째 에피소드에서, 호머가 실수로 "세 번째 차원"에 발을 헛디딘 직후 방정식 P = NP가 보입니다.

초등학교 시즌 2의 두 번째 에피소드에서 "Solve for X" 셜록과 왓슨은 P 대 NP를 풀려고 시도하던 수학자들의 살인 사건을 조사합니다.^[55][56]

참고 항목

• 게임의 복잡성
• 수학의 미해결 문제 목록
• 독특한 게임 추측
• 컴퓨터 과학의 미해결 문제

메모들

참고문헌

원천

• Rachel Crowell (28 May 2021). "The Top Unsolved Questions in Mathematics Remain Mostly Mysterious Just one of the seven Millennium Prize Problems named 21 years ago has been solved". www.scientificamerican.com. Retrieved 21 June 2021. This problem concerns the issue of whether questions that are easy to verify (a class of queries called NP) also have solutions that are easy to find (a class called P).
• Hosch, William L (11 August 2009). "P versus NP problem mathematics". Encyclopædia Britannica. Retrieved 20 June 2021.
• "P vs NP Problem". www.claymath.org (Cook, Levin). Retrieved 20 June 2021. Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem...

추가읽기

• Cormen, Thomas (2001). Introduction to Algorithms. Cambridge: MIT Press. ISBN 978-0-262-03293-3.
• Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676.
• Goldreich, Oded (2010). P, NP, and NP-Completeness. Cambridge: Cambridge University Press. ISBN 978-0-521-12254-2. 온라인 초안
• Immerman, Neil (1987). "Languages that Capture Complexity Classes". SIAM Journal on Computing. 16 (4): 760–778. CiteSeerX 10.1.1.75.3035. doi:10.1137/0216051.
• Papadimitriou, Christos (1994). Computational Complexity. Boston: Addison-Wesley. ISBN 978-0-201-53082-7.

외부 링크

• Fortnow, L.; Gasarch, W. "Computational complexity".
• ACM의 2017년 박사학위 논문상 수상자인 아비아드 루빈스타인의 P와 NP 사이의 근사 경도.
• "P vs. NP and the Computational Complexity Zoo". 26 August 2014. Archived from the original on 24 November 2021 – via YouTube.