P-NP 문제

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

P-NP 문제는 계산 복잡도 이론에서 P와 NP라는 두 복잡도 종류 간의 관계를 묻는 미해결 문제이다. P는 다항 시간 내에 해결 가능한 문제들의 집합이고, NP는 해답이 주어졌을 때 다항 시간 내에 검증 가능한 문제들의 집합이다. P가 NP의 진부분집합인지, 즉 P≠NP인지가 주요 질문이며, 이는 1971년 스티븐 쿡에 의해 처음 제기되었다. P-NP 문제 해결 시, 계산 복잡도 이론의 발전과 실질적인 계산적 이점을 가져올 수 있다. 현재까지 다양한 증명 시도가 있었지만, 대부분의 증명 기술은 P≠NP를 증명하기에 불충분하다는 것이 밝혀졌다. P≠NP일 것이라는 예측이 지배적이지만, P=NP를 예상하는 연구자도 존재한다. P-NP 문제와 관련된 다양한 문제들이 존재하며, EXPTIME, #P, 그리고 결정 불가능한 문제 등이 있다.

더 읽어볼만한 페이지

1956년 컴퓨팅 - 다트머스 회의
다트머스 회의는 1956년 다트머스 대학교에서 열린 인공지능 연구를 위한 최초의 회의로, 존 매카시, 마빈 민스키 등이 참여하여 "인공지능"이라는 용어를 처음 사용하고 지능의 모든 측면을 기계로 시뮬레이션할 수 있다는 아이디어를 제시하며 인공지능 연구의 초석을 다졌다.
1956년 컴퓨팅 - 촘스키 위계
촘스키 위계는 노엄 촘스키가 제시한 형식 문법 분류 체계로, 생성 규칙 제약 조건에 따라 무제약 문법, 문맥 의존 문법, 문맥 자유 문법, 정규 문법으로 나뉘며, 언어 복잡성과 오토마타 유형에 따라 구분되는 형식 언어 및 오토마타 이론의 핵심 개념이다.
컴퓨터 과학의 미해결 문제 - 인공지능
인공지능은 인간의 지능적 행동을 모방하는 컴퓨터 시스템으로, 인간 수준의 일반 지능을 가진 강인공지능과 특정 문제 해결에 특화된 약인공지능으로 나뉘며, 딥러닝 기술 발전으로 다양한 분야에서 성과를 거두고 있지만 윤리적, 사회적 문제에 대한 고려가 필요하다.
컴퓨터 과학의 미해결 문제 - 이산 로그
이산 로그는 유한군에서 이산 거듭제곱의 지수를 찾는 역함수로, 소수 p를 법으로 하는 정수 모듈러 곱셈 그룹에서 계산적으로 풀기 어려운 문제이며, 현대 암호 시스템의 안전성 기반이지만 양자 알고리즘으로 효율적 해결이 가능하여 양자 내성 암호 연구가 필요하다.
밀레니엄 문제 - 푸앵카레 추측
푸앵카레 추측은 1904년 앙리 푸앵카레가 제기한 3차원 다양체의 위상적 성질에 관한 문제로, 2002년 그리고리 페렐만이 증명했으며, 기본군이 자명한 3차원 다양체가 3차원 구와 위상동형인지 묻는 질문이다.
밀레니엄 문제 - 리만 가설
리만 가설은 리만 제타 함수의 자명하지 않은 모든 영점의 실수부가 1/2이라는 추측으로, 힐베르트 문제와 클레이 수학 연구소의 밀레니엄 문제 중 하나이며 정수론과 복소해석학을 연결하는 다양한 수학적 명제들과 동치이다.

P-NP 문제
개요
분야	계산기 과학, 이론 컴퓨터 과학
성격	미해결 문제
공식 명칭	P 대 NP 문제
문제 내용	만약 어떤 문제에 대한 해답을 다항 시간 내에 검증할 수 있다면, 그 문제를 다항 시간 내에 풀 수 있는가?
제안자	스티븐 쿡(공식적), 레오니트 레빈(독립적)
제안 시기	1971년 (쿡), 1973년 (레빈)
상금	100만 미국 달러 (클레이 수학연구소)
중요성	만약 P=NP라면, 현재 암호화 시스템은 무용지물이 됨. 많은 최적화 문제들을 효율적으로 해결할 수 있게 됨.
배경
복잡도 종류	P NP NP-완전 NP-난해
관련 문제	NP-완전 문제 목록 밀레니엄 문제
가정된 해답
일반적인 믿음	P ≠ NP
증명 시도	상대화 장벽 자연 증명 장벽 대수화 장벽
관련 인물
주요 연구자	스티븐 쿡 레오니트 레빈 리처드 카프 커트 괴델

2. 역사

P-NP 문제는 1971년 스티븐 쿡이 〈정리 증명 절차의 복잡성〉 논문에서 처음으로 엄밀하게 정의하였다.^[66] 그러나 이 문제가 명확하게 정의되기 전에도 관련된 개념들이 언급되었다.

1955년, 수학자 존 내시는 미국 국가안보국(NSA)에 보낸 편지에서 암호 해독의 어려움에 대해 언급했다. 그는 충분히 복잡한 암호를 해독하려면 키 길이에 대한 지수적인 시간이 필요할 것이라고 추측했는데,^[67] 이는 P≠NP 예상과 관련이 있다.

1956년에는 쿠르트 괴델이 존 폰 노이만에게 보낸 편지에서 정리 증명 문제의 복잡성에 대해 질문했다.^[68] 괴델은 이 문제가 2차 시간 안에 풀릴 수 있는지 물었는데, 이는 현대적인 관점에서 Co-NP-완전 문제에 해당한다.

이처럼 P-NP 문제의 초기 형태는 1950년대에 이미 논의되었으며, 1971년 스티븐 쿡의 논문을 통해 비로소 정식화되었다.

2. 1. 증명 시도와 어려움

계산 복잡도 이론에서 알려진 거의 모든 증명 기술은 P≠NP를 증명하기에 불충분하며, 새로운 기술적 접근 방식이 필요한 상황이다. 다음은 기존 증명 기술들의 한계를 나타내는 표이다.

분류	정의	P≠NP 증명 한계
상대화 증명	모든 알고리즘이 "오라클"이라는 고정된 서브루틴에 쿼리 가능. 오라클 실행 시간은 알고리즘 실행 시간에 불포함.	1975년 베이커, 길, 솔로베이는 일부 오라클에서는 P=NP, 다른 오라클에서는 P≠NP임을 보였다.^[44] 상대화 증명은 모든 오라클에 대해 참인 명제만 증명 가능하므로, P-NP 문제 해결 불가.
자연 증명	1993년 알렉산더 라즈보로프와 스티븐 루디치가 정의한 회로 복잡도 하한 증명 기술.^[45]	라즈보로프와 루디치는 일방향 함수가 존재한다면 P와 NP는 자연 증명 방식으로 구별 불가능함을 보였다. 일방향 함수 존재 증명은 P≠NP보다 강력한 명제이므로, 자연 증명만으로 P-NP 문제 해결 불가.
대수화 증명	알고리즘 연산을 대수적, 산술 기호로 변환 후 작동 방식 분석.	2008년 스콧 아론슨과 아비 위그더슨은 "산술화"가 P=NP 해결에 불충분함을 보였다.^[46] 산술화는 IP=PSPACE 증명에 사용된 기술적 도구였으나, P=NP 및 기타 시간 복잡도 문제 해결에는 부적합.

이러한 한계는 NP-완전 문제가 유용한 이유이기도 하다. 만약 NP-완전 문제에 대한 다항 시간 알고리즘이 발견된다면, 이는 기존 증명 기술의 한계를 극복하고 P=NP 문제를 해결하는 실마리가 될 수 있다.

P≠NP를 증명하기 위해서는 상대화, 자연스러운 증명, 대수화의 한계를 극복하는 새로운 증명 기법이 필요하다. 현재 대수 기하를 이용한 방법, 수학 기초론에 의한 방법 등이 연구되고 있지만, 이들 역시 한계가 있을 수 있으며, 증명 기법에 대한 더 깊은 이해가 요구된다.

칸토어가 1891년에 고안한 대각선 논법은 복잡성 클래스를 분리하기 위해 초창기부터 1970년대 말까지 이용된 증명 기법이다. 이는 한쪽 클래스의 보편 함수이면서 다른 쪽 클래스에 속하는 것을 구성하고, 그 대각선 부분에 주목함으로써 복잡성 클래스를 분리하는 것으로, P≠EXPTIME을 증명할 때 등에 적용되었다. 이러한 증명 기법의 특징은 "상대화"라고 불리는 성질을 보존한다는 것이다. 복잡성 클래스 C, D에 대해 대각선 논법으로 C≠D가 증명되었다면, 그 증명은 오라클 A를 가진 계산 모델에서도 통용되므로, C^A≠D^A가 동시에 성립한다. 마찬가지로, 대각선 논법으로 C＝D가 증명된 경우에는 C^A＝D^A가 어떤 A에 대해서도 성립한다.

그러나, 베이커, 길, 솔로베이는 다음을 보였다.

P^A≠NP^A가 되는 오라클 A와, P^B＝NP^B가 되는 오라클 B가 존재한다.^[44]

이 결과로 인해, 대각선 논법처럼 상대화가 가능한 증명 기법으로는 P≠NP를 원리적으로 증명할 수 없다는 것이 판명되었다.

1980년대에는 집합론적 기법이 아닌 회로 복잡도에 주목하는 새로운 증명 기법인 "자연스러운 증명"이 개발되었다. 이는 AC⁰≠NC¹ , mP/poly≠NP 등의 성과를 냈다.

그러나, 라즈보로프와 루디치는 다음을 제시했다.

소인수분해의 어려움을 가정하면, 자연스러운 증명으로는 P/poly≠NP를 증명할 수 없다.^[45]

"자연스러운 증명"은 자연스러운 발상에 기초한 증명 전략이며, 지금까지 얻어진 복잡성 클래스의 분리에 관한 거의 모든 증명에 이용되었다. 그러나, 이러한 증명 기법으로는 P≠NP를 원리적으로 증명할 수 없다는 것이 판명되었다. 라즈보로프와 루디치는 이 성과로 2007년 괴델상을 수상했다.

"산술화"는 집합론적이고 자연스러운 증명이 아닌 증명 기법으로, 논리식을 유한체 또는 유한환 상의 다항식으로 바꿔 고찰하는 것이다.

하지만, 아론슨과 위그더슨은 이러한 증명 방법으로는 P≠NP를 증명하는 것이 불가능하다는 것을 밝혔다.^[46]

현재 P≠NP를 증명하기 위해서는 상대화되지 않고 자연스러운 증명이 아니며, 대수화할 수 없는 증명 기법이 필요하다고 여겨지고 있다. 그러한 증명 기법의 후보는 다음과 같다.

NEXP $\not\subseteq$ ACC⁰ 에서의 기법
대수 기하를 이용한 방법
수학 기초론에 의한 방법

3. 핵심 개념

계산 복잡도 이론에서 복잡도 종류 P와 NP의 관계는 연구된다. 계산 복잡도 이론은 주어진 문제를 해결하기 위해 필요한 자원(시간, 공간)을 다루는 계산 이론의 한 분야이다.

일반적으로 컴퓨터 모델은 ''결정적''이고 ''순차적''이라고 가정한다.

'''클래스 P''': 입력 크기에 대한 다항식 시간 내에 결정적 순차 기계에서 해결 가능한 모든 ''결정 문제''로 구성된다.
'''클래스 NP''': 다항 시간 내에 긍정적인 해답을 확인할 수 있거나, 비결정적 기계에서 다항식 시간 내에 해결책을 찾을 수 있는 모든 결정 문제로 구성된다.^[8]

P는 결정적 튜링 머신에서 다항 시간으로 판정 가능한 문제의 클래스이고, NP는 'Yes'가 되는 증거(Witness)가 주어졌을 때 다항 시간으로 그 정당성을 검증할 수 있는 문제의 클래스이다. 다항 시간으로 판정 가능한 문제는 다항 시간으로 검증 가능하므로, P⊆NP임은 명백하지만, P가 NP의 진부분집합인지 여부는 명확하지 않다.

P ⊆ NP 이며, 이 두 클래스의 관계(P=NP 인지 혹은 P≠NP 인지)는 이론 컴퓨터 과학에서 가장 큰 미해결 과제이다.

윌리엄 가사치의 여론 조사에 따르면, P ≠ NP라고 믿는 연구자들이 점차 증가하는 추세이다.^[9]^[10]^[11] 2019년에는 전문가의 99%가 P ≠ NP라고 믿는 것으로 나타났다.^[11] 그러나 이러한 여론 조사가 P = NP인지 여부를 증명하는 것은 아니다.

P=NP가 증명될 경우, 다항 시간으로 검증 가능한 문제는 모두 다항 시간으로 판정 가능함을 의미하며, 다양한 분야에 효율적인 계산 알고리즘이 주어질 가능성이 있다. 그러나 많은 연구자들이 오랫동안 노력했음에도 불구하고, 그러한 효율적인 알고리즘은 발견되지 않았다.

존 내시는 1955년 NSA에 보낸 편지에서 복잡한 암호 해독에는 키 길이의 지수 시간이 소요될 것이라고 언급했다.^[62]

도널드 커누스는 P=NP를 예상하는 연구자 중 한 명이다.^[61] 그는 P≠NP 증명 시도가 모두 실패했고, NP 문제를 n^M 단계(M은 매우 큰 유한한 값)로 푸는 알고리즘이 존재할 가능성을 언급했다. 그러나 그는 동시에 P=NP가 증명되더라도 실용적으로 도움이 되지 않을 수 있다고 말했다.

3. 1. P (복잡도)

계산 복잡도 이론에서 클래스 P는 결정적 튜링 머신에서 다항식 시간 안에 해결 가능한 모든 결정 문제로 구성된다.^[8] 즉, 문제의 크기가 n일 때, 어떤 상수 k에 대해 O(n^k) 시간 안에 답을 구할 수 있는 문제들이다.

P-NP 문제에서 P는 NP와 같은지에 대한 질문은 이론 컴퓨터 과학에서 가장 큰 미해결 과제 중 하나이다.^[8] 윌리엄 가사치는 2002년 이후 이 질문에 대해 연구자들을 대상으로 여론 조사를 실시했는데,^[9]^[10]^[11] 2019년에는 88%가 P ≠ NP라고 믿었으며, 이는 2012년의 83%, 2002년의 61%에 비해 증가한 수치이다. 전문가로 제한하면 2019년 답변은 99%가 P ≠ NP라고 믿는 것으로 나타났다.^[11] 그러나 이러한 여론 조사가 P = NP인지 여부를 증명하는 것은 아니다. 가사치 본인은 "이것은 P=?NP를 해결하거나 언제 해결될지 아는 데 더 가까워지지는 않지만, 이 시대의 주관적인 의견에 대한 객관적인 보고서가 되려고 한다."라고 말했다.^[11]

도널드 커누스는 P=NP라고 예상하는 연구자 중 한 명으로, P≠NP를 증명하려는 시도가 모두 실패했다는 점과, NP 문제를 n^M 단계로 푸는 알고리즘이 있다고 가정할 때 M이 매우 큰 유한한 값을 가질 수 있다는 점을 논거로 들었다.^[61] 그러나 그는 동시에 P=NP가 증명되더라도 실용적으로 도움이 되지 않을 수 있다고 말했다.^[61]

1956년 쿠르트 괴델은 존 폰 노이만에게 보낸 편지에서 정리 증명을 2차 또는 선형 시간 내에 풀 수 있는지 질문하고, 이것이 가능하다면 수학의 새로운 정리를 발견하는 것을 자동화할 수 있을 것이라고 지적했다.^[63]

3. 2. NP (복잡도)

'''NP'''는 비결정적 튜링 기계로 다항 시간 안에 풀 수 있는 문제들의 집합이다. 또는 어떤 해답이 주어졌을 때, 그 해답이 올바른지 다항 시간 안에 확인할 수 있는 문제들의 집합이다.^[8]

부분집합 합 문제는 쉽게 풀이법을 확인할 수 있지만, 답을 구하기는 어려울 수 있는 문제의 예시이다. 이 문제는 어떤 정수들의 집합이 주어졌을 때, 공집합이 아닌 부분집합 중 적어도 하나 이상의 부분집합의 합계가 0이 될 수 있는지 알아내는 문제이다. 예를 들어 {−2, −3, 15, 14, 7, −10}이라는 집합이 주어졌을 때, 부분집합 {-2, -3, -10, 15}의 합계가 0이므로 이 문제에 대한 답은 '그렇다'이다. 이 부분집합이 문제의 답이 된다는 것을 확인하기 위해서는 3번의 덧셈만으로 충분하다. 반면 처음 주어진 집합에서 원소의 합이 0이 되도록 하는 부분집합을 찾으려면 일일이 부분집합을 만들고, 각 원소들끼리 더하여 0이 되는지 확인해야 하기 때문에 쉽지 않다. 이러한 조건을 만족하는 부분집합을 다항 시간 안에 찾아내는 알고리즘은 현재까지 알려져 있지 않다. 따라서 부분집합 합 문제는 NP에 속한다.

계산 복잡도 이론에서 복잡도 종류 P와 NP의 관계는 연구된다. 계산 복잡도 이론은 주어진 문제를 해결하기 위해 계산하는 동안 필요한 자원을 다루는 계산 이론의 한 분야이다. 가장 일반적인 자원은 시간(문제를 해결하는 데 걸리는 단계 수)과 공간(문제를 해결하는 데 필요한 메모리 양)이다.

클래스 P는 입력 크기에 대한 다항식 시간 내에 결정적 순차 기계에서 해결 가능한 모든 결정 문제로 구성된다. NP는 올바른 정보가 주어질 경우 다항 시간 내에 긍정적인 해답을 확인할 수 있는 모든 결정 문제 또는 동등하게 비결정적 기계에서 다항식 시간 내에 해결책을 찾을 수 있는 모든 결정 문제로 구성된다.^[8]

클래스 P는 결정적 튜링 머신에서 다항 시간으로 판정 가능한 판정 문제의 클래스이며, 클래스 NP는 'Yes'가 되는 증거(Witness라고 한다)가 주어졌을 때, 다항 시간으로 Witness의 정당성을 판정(검증이라고 한다)할 수 있는 문제의 클래스이다. 다항 시간으로 판정 가능한 문제는 다항 시간으로 검증 가능하므로, P⊆NP임은 명백하지만, P가 NP의 진부분집합인지 여부는 명확하지 않다. 아직 증명되지 않았지만, 많은 연구자는 P≠NP라고 믿고 있다. 그리고 이 클래스 P와 클래스 NP가 같지 않다는 예상을 "P≠NP 예상"이라고 한다.

n^2 \times n^2

크기의 불완전한 스도쿠 격자가 주어졌을 때, 각 행, 열,

n \times n

사각형이 1부터

n^2

까지의 정수를 포함하는 유효한 해가 적어도 하나 존재하는가? 하는 예/아니오 문제를 생각해 보자. 이 일반화된 스도쿠 문제의 "예" 인스턴스는 후보 해가 주어지면 쉽게 확인할 수 있다. 하지만, 이 문제의 모든 인스턴스에 대해 "예" 또는 "아니오"로 정확하게 대답할 수 있는 다항 시간 알고리즘이 존재하는지는 알려져 있지 않다. 따라서 일반화된 스도쿠는 NP에 속하지만(빠르게 검증 가능), P에 속할 수도 있고(빠르게 해결 가능) 아닐 수도 있다.

3. 3. NP-완전 (NP-complete)

NP-완전은 P-NP 문제에서 중요한 개념 중 하나인데, NP-완전 문제란 모든 NP 문제가 다항 시간 안에 변환될 수 있는 NP 문제를 말한다.^[12] 쉽게 표현하자면, NP-완전 문제는 다른 어떤 NP 문제들보다 해결하기 어려운 NP 문제이다.

NP-완전 문제를 정의하기 위해 다음 두 가지 개념을 사용한다.

NP: 어떤 문제의 해가 주어졌을 때, 그 해가 맞는지 다항 시간 안에 확인할 수 있는 문제들의 집합이다. 예를 들어, 일반화된 스도쿠 문제는 해가 주어지면 쉽게 확인할 수 있지만, 다항 시간 안에 해를 찾는 알고리즘은 아직 알려져 있지 않다.
다항 시간 환원: 어떤 문제 A를 다른 문제 B로 변환하는 다항 시간 알고리즘이 존재할 때, 문제 A는 문제 B로 다항 시간 환원 가능하다고 한다.

NP-완전 문제는 다음 두 가지 조건을 만족하는 문제이다.

1. NP에 속한다.

2. 모든 NP 문제를 다항 시간 안에 NP-완전 문제로 환원할 수 있다.

NP-완전 문제 중 하나라도 다항 시간 안에 풀 수 있다면, 모든 NP 문제를 다항 시간 안에 풀 수 있게 된다. 즉, P=NP가 된다.

최초로 NP-완전으로 증명된 문제는 불만족 문제(SAT)이다. 쿡-레빈 정리에 따르면, 모든 NP 문제는 다항 시간 안에 불만족 문제로 변환될 수 있다. 이후 축소에 의한 증명을 통해 스도쿠와 같은 다른 많은 문제들이 NP-완전임이 밝혀졌다.

NP-완전을 설명하는 데는 여러 가지 동등한 방법이 있다. 유한 알파벳 Σ에 대한 언어 ''L''이 NP-완전인 것은 다음 두 가지 조건이 충족될 때, 그리고 그 때만 NP-완전이다.

1. ''L'' ∈ NP; 그리고

2. NP에 있는 모든 ''L'''은 ''L''로 다항 시간 내에 환산될 수 있다(

L' \leq_{p} L

로 표기).

L' \leq_{p} L

는 다음 두 가지 조건이 충족될 때, 그리고 그 때만 성립한다.

모든 ''w'' in Σ*에 대해 $(w\in L' \Leftrightarrow f(w)\in L)$ 를 만족하는 ''f'' : Σ* → Σ*가 존재하고; 그리고
모든 입력 ''w''에 대해 테이프에 ''f''(''w'')를 기록하고 정지하는 다항 시간 튜링 기계가 존재한다.

또는, ''L'' ∈ NP이고, 다른 NP-완전 문제가 ''L''로 다항 시간 내에 환산될 수 있다면, ''L''은 NP-완전이다. 이는 새로운 문제가 NP-완전임을 증명하는 일반적인 방법이다.

1971년 스티븐 쿠크가 충족 가능성 문제를 시작으로 NP-완전 개념을 정식화했으며, 이후 수천 개 이상의 문제가 NP-완전임이 증명되었다.

3. 4. NP-난해 (NP-hard)

NP-난해 문제는 모든 NP 문제를 다항 시간 안에 해당 문제로 환원할 수 있는 문제이다. NP-난해 문제는 NP에 속할 필요는 없으며, 이는 다항 시간 안에 검증 가능한 해답을 가질 필요가 없다는 것을 의미한다.

쉽게 표현하면, 어떤 NP 문제라도 NP-난해 문제로 변환할 수 있다. 만약 어떤 NP-난해 문제가 NP에도 속한다면, 그 문제는 NP-완전 문제에 해당한다.^[12]

4. P-NP 문제의 중요성

P-NP 문제는 해결 방향에 따라 이론 및 실질적인 면에서 큰 영향을 줄 수 있기 때문에 많은 관심을 받고 있다.

클래스 P는 결정적 튜링 머신에서 다항 시간 안에 판정 가능한 판정 문제의 집합이며, 클래스 NP는 '예'라는 답에 대한 증거(Witness)가 주어졌을 때 다항 시간 안에 그 증거의 정당성을 검증할 수 있는 문제의 집합이다. 모든 다항 시간 판정 문제는 다항 시간 검증이 가능하므로 P⊆NP는 명백하지만, P가 NP의 진부분 집합인지, 즉 P≠NP인지는 아직 밝혀지지 않았다. 많은 연구자들은 P≠NP일 것이라고 예상하고 있다.

만약 P=NP로 증명된다면, 다항 시간 안에 검증 가능한 모든 문제가 다항 시간 안에 판정 또한 가능하다는 것을 의미한다. 이는 현재 효율적인 알고리즘이 없는 다양한 문제들에 대해 효율적인 계산 알고리즘이 존재할 가능성을 제시한다. 그러나 수많은 연구자들이 오랫동안 노력했음에도 불구하고 이러한 효율적인 알고리즘은 발견되지 않았다. NP에 속하는 수천 개의 문제들이 P=NP 증명 즉시 모두 다항 시간에 풀린다는 것은 쉽게 받아들이기 어렵다. 경험적으로, 어떤 NP 완전 문제의 입력 n 비트에 대한 최적의 계산량이 O(kⁿ・''poly''(n,))일 때, 밑 k를 개선하려는 시도조차 어느 정도 진전 후에는 한계에 부딪히는 것으로 알려져 있다. 이러한 점들이 P≠NP 예상의 주요 근거로 작용한다.

반면, P=NP라고 예상하는 연구자들도 존재한다. 도널드 커누스는 P≠NP를 증명하려는 시도들이 모두 실패했다는 점과, NP 문제를 n^M 단계 (M은 매우 큰 수)로 푸는 알고리즘이 존재할 가능성을 언급하며 P=NP일 수 있다고 주장한다.^[61] 그러나 그는 동시에 P=NP가 증명되더라도, 그 증명이 비구성적일 가능성이 높아 실용적으로는 도움이 되지 않을 것이라고 말한다.^[61] 그는 존재가 증명되었지만 현실적으로 구현이 불가능한 알고리즘의 예시들을 제시하며 이러한 주장을 뒷받침한다.

4. 1. P ≠ NP의 결과

P ≠ NP가 증명된다면, 이는 NP에 속하는 문제들 중 다항 시간 알고리즘으로 풀 수 없는 문제들이 있다는 것을 의미한다.^[41] 이는 계산 복잡도 이론에서 큰 발전이며, 앞으로의 연구 방향을 제시할 것이다. 또한, 많은 일반적인 문제들을 효율적으로 해결할 수 없다는 것을 보여주기 때문에, 연구자들이 부분적인 해결책이나 다른 문제에 대한 해결책을 찾는 데 집중하도록 유도할 수 있다.^[41] 실제로 P ≠ NP라는 믿음 하에 이러한 연구가 이미 많이 진행되었다.^[41]

P ≠ NP는 NP에 속하는 어려운 문제들의 평균 사례 복잡도에 대한 가능성을 열어둔다. 예를 들어, SAT 문제는 최악의 경우 지수 시간이 걸릴 수 있지만, 무작위로 선택된 대부분의 경우에는 효율적으로 해결될 수 있다.^[42] 러셀 임파글리아초는 평균 사례 복잡도에 대한 다양한 가능성을 설명하는 다섯 가지 가상적인 "세계"를 제시했다.^[42] 이 중 P ≠ NP이지만 NP의 모든 문제가 평균적으로 해결 가능한 "세계"를 "휴리스티카"라고 부른다.^[42]

P=NP 문제 해결을 위한 노력은 여러 새로운 기술을 낳았다. 특히, 기존 증명 기술로는 이 문제를 해결하기 어렵다는 것을 보여주는 연구 결과들이 나오면서, 새로운 접근 방식이 필요하다는 점이 시사되고 있다.

계산 복잡도 이론에서 알려진 거의 모든 증명 기술은 다음 분류 중 하나에 속하며, 이들 모두 P≠NP를 증명하기에 불충분하다는 것이 밝혀졌다.

분류

정의

상대화 증명

고정된 서브루틴("

이러한 장벽들은 NP-완전 문제가 중요한 또 다른 이유를 제시한다. 만약 NP-완전 문제에 대한 다항 시간 알고리즘을 찾을 수 있다면, 이는 위에서 언급된 한계들을 극복하는 방식으로 P=NP 문제를 해결할 수 있을 것이다.

일부 컴퓨터 과학자들은 P 대 NP 문제가 ZFC와 독립적일 수 있다고 추측한다.

4. 2. 다른 문제와의 관계

NP-완전 문제는 다른 모든 NP 문제가 다항 시간 내에 변환될 수 있고, 그 해답이 여전히 다항 시간 내에 검증 가능한 문제이다. 비공식적으로, NP-완전 문제는 NP 문제 중 가장 "어려운" 문제이다. 예를 들어, 불만족 문제는 쿡-레빈 정리에 의해 NP-완전이며, 만약 어떤 NP-완전 문제가 P에 속한다면 P=NP가 된다.^[12]

1975년 리처드 E. 래드너(Richard E. Ladner)는 P≠NP라면 P에도 속하지 않고 NP-완전도 아닌 NP 문제, 즉 NP-중간(NPI) 문제가 존재함을 증명했다.^[40] 그래프 동형 문제, 이산 로그 문제, 정수 인수분해 문제는 NPI 문제로 여겨지는 예시이다.^[40]

그래프 동형 문제는 두 그래프가 동형인지 판별하는 문제이다. 그래프 동형 문제가 P, NP-완전, NPI 중 어디에 속하는지는 알려지지 않았지만, NP-완전은 아닌 것으로 추정된다.^[20] 만약 그래프 동형이 NP-완전이라면 다항 시간 계층이 축소되는데,^[21] 이는 일어나지 않을 것으로 널리 믿어지기 때문이다.

정수 인수분해 문제는 주어진 정수의 소인수분해를 찾는 문제이다. 효율적인 정수 인수분해 알고리즘은 알려져 있지 않으며, 이는 RSA 암호 시스템의 기반이 된다. 정수 인수분해 문제는 NP와 co-NP에 속한다.^[23] 만약 이 문제가 NP-완전이라면 다항 시간 계층이 축소된다 (NP = co-NP).

NP 문제의 보문제들로 구성된 복잡도 클래스는 Co-NP이다. NP≠co-NP라면 P≠NP가 된다.

; NP-완전

: 스티븐 쿠크가 1971년에 정식화한 개념으로, NP에 속하면서 다른 모든 NP 문제가 다항 시간 환원되는 문제이다. 충족 가능성 문제를 비롯한 수천 개의 문제가 NP-완전임이 증명되었다. 이 중 하나라도 P에 속하면 P=NP가 된다.

; NP-완전에 포함되지 않는 문제

: NP-(P∪NP-완전)인 문제의 클래스를 NPI라고 한다. P≠NP라면 NPI는 공집합이 아님이 증명되었다. 그래프 동형 문제가 이러한 문제의 후보이다.

; Co-NP

: NP 문제의 보문제로 구성된 클래스이다. NP≠co-NP라면 P≠NP가 된다.

5. P와 NP의 정의

계산 복잡도 이론에서 P와 NP는 복잡도 종류로, 주어진 문제를 해결하기 위해 필요한 자원(시간, 공간)을 기준으로 문제를 분류한다. 여기서 '시간'은 문제를 해결하는 데 걸리는 단계 수를, '공간'은 필요한 메모리 양을 의미한다.

이러한 분석을 위해서는 계산 모델이 필요한데, 일반적으로 사용되는 모델은 '결정적'이고 '순차적'인 컴퓨터이다. 즉, 컴퓨터의 현재 상태와 입력이 주어지면 다음에 수행할 작업이 하나뿐이며, 작업을 순서대로 하나씩 처리한다.

P는 입력 크기에 대해 다항식 시간 안에 결정적 순차 기계(예: 튜링 머신)에서 해결 가능한 모든 결정 문제들의 집합이다. NP는 올바른 정보가 주어지면 다항 시간 안에 긍정적인 해답을 확인하거나, 비결정적 기계에서 다항식 시간 안에 해결책을 찾을 수 있는 모든 결정 문제들의 집합이다.^[8]

P가 NP의 부분집합(P ⊆ NP)인 것은 분명하다. 이론 컴퓨터 과학에서 가장 큰 미해결 문제 중 하나는 바로 P와 NP가 같은지(P = NP) 아니면 다른지(P ≠ NP)에 대한 것이다.

2002년 이후 윌리엄 가사치는 이 문제에 대해 연구자들을 대상으로 여론 조사를 실시했는데,^[9]^[10]^[11] 2019년에는 88%가 P ≠ NP라고 답했으며, 전문가들은 99%가 P ≠ NP라고 믿는 것으로 나타났다.^[11] 하지만 이러한 여론 조사가 P = NP 문제의 해결을 의미하는 것은 아니다.

NP-완전 문제에 대한 알려진 알고리즘은 다항 시간 내에 실행되지 않는다. 그러나 P = NP라면 NP-완전 문제에 대해 다항 시간 알고리즘이 존재하며, 이 알고리즘은 긍정적인 경우에 다항 시간 내에 실행될 것이다. 하지만, 이러한 알고리즘은 부정적인 경우의 실행 시간이 다항식이 아니기 때문에 다항 시간으로 간주되지 않는다. 레오니드 레빈이 제안한 알고리즘은 이러한 예시 중 하나이며, SUBSET-SUM을 올바르게 수용하지만, P = NP인 경우에만 SUBSET-SUM에 속하는 입력에 대해 다항 시간 내에 실행된다.

P = NP인 경우에도 이 알고리즘은 매우 비효율적일 수 있다. 예를 들어 SUBSET-SUM을 다항 시간 내에 해결하는 가장 짧은 프로그램의 길이가 ''b'' 비트라면, 레빈의 알고리즘은 2^''b'' − 1개 이상의 다른 프로그램을 먼저 시도해야 한다.

5. 1. 결정 문제

계산 복잡도 이론에서 '''결정 문제'''는 입력에 대해 "예" 또는 "아니오"로 답하는 문제이다. 클래스 P는 입력 크기에 대한 다항식 시간 내에 결정적 순차 기계에서 해결 가능한 모든 결정 문제로 구성된다. NP는 올바른 정보가 주어질 경우 다항 시간 내에 긍정적인 해답을 확인할 수 있는 모든 결정 문제이거나, 비결정적 기계에서 다항식 시간 내에 해결책을 찾을 수 있는 모든 결정 문제로 구성된다.^[8]

5. 2. 튜링 머신

알고리즘의 실행을 나타내는 데 사용되는 추상적인 계산 모델은 튜링 머신이다. 결정적 다항 시간 튜링 머신은 다음 두 가지 조건을 만족한다.^[8]

# 모든 입력 ''w''에서 중지한다.

#

T_M(n)\in O(n^k)

을 만족하는

k \in N

이 존재한다. 여기서 ''O''는 빅 오 표기법을 나타낸다.

:

T_M(n) = \max\{ t_M(w) : w\in\Sigma^{*}, |w| = n \}

:

t_M(w) = \text{ number of steps }M\text{ takes to halt on input }w.

NP는 비결정적 튜링 머신을 사용하여 유사하게 정의될 수 있다.^[8]

5. 3. 다항 시간

계산 복잡도 이론에서 문제의 크기 n에 대해, 어떤 상수 k에 대해 O(n^k) 시간 안에 문제를 해결할 수 있는 경우를 다항 시간이라고 한다. P는 입력 크기에 대한 다항식 시간 내에 결정적 순차 기계에서 해결 가능한 모든 결정 문제로 구성된다.^[8]

예를 들어, 어떤 자연수 ''x''가 합성수인지 판별하는 문제는 ''x''가 다음 집합에 속하는지 확인하는 것과 같다.

:

\mathrm{COMPOSITE} = \left \{x\in\mathbb{N} \mid x=pq \text{ for integers } p, q > 1 \right \}

COMPOSITE가 위에 정의된 조건을 만족하는지 확인하여 COMPOSITE ∈ NP임을 보일 수 있다(자연수를 이진 표현으로 식별하는 경우).^[50]

5. 4. P의 정의

계산 복잡도 이론에서 '''P'''는 결정적 튜링 머신으로 다항식 시간 안에 풀 수 있는 결정 문제들의 집합이다.^[8]

어떤 문제가 입력 문자열의 길이가 ''n''일 때 최대

cn^k

단계 내에 정답을 생성하는 알고리즘(예: 튜링 머신)이 존재하고, 여기서 ''k''와 ''c''는 입력 문자열과 독립적인 상수라면, 해당 문제는 ''다항 시간'' 내에 해결될 수 있으며, 이를 클래스 P에 속한다고 한다.

공식적으로, P는 결정적 다항 시간 튜링 머신에 의해 결정될 수 있는 언어의 집합으로 정의된다. 즉,

:

\mathbf{P} = \{ L : L=L(M) \text{ for some deterministic polynomial-time Turing machine } M \}

이며, 여기서

:

L(M) = \{ w\in\Sigma^{*}: M \text{ accepts } w \}

이고, 결정적 다항 시간 튜링 머신은 다음 두 가지 조건을 만족하는 결정적 튜링 머신 ''M''이다.

# ''M''은 모든 입력 ''w''에서 중지한다.

#

T_M(n)\in O(n^k)

을 만족하는

k \in N

이 존재하며, 여기서 ''O''는 빅 오 표기법을 나타낸다.

::

T_M(n) = \max\{ t_M(w) : w\in\Sigma^{*}, |w| = n \}

::

t_M(w) = \text{ number of steps }M\text{ takes to halt on input }w.

5. 5. NP의 정의

계산 복잡도 이론에서 NP(Non-deterministic Polynomial time)는 비결정적 튜링 기계로 다항 시간 안에 풀 수 있는 결정 문제들의 집합이다.^[8] 또는 해답이 주어졌을 때 다항 시간 안에 그 해답을 검증할 수 있는 결정 문제들의 집합이다.

예를 들어, 부분집합 합 문제는 어떤 정수들의 집합이 주어졌을 때 부분집합의 합이 0이 되는 경우가 있는지 판별하는 문제인데, {-2, -3, -10, 15}와 같이 답이 되는 부분집합을 찾기는 어렵지만, 이 부분집합의 합이 0이라는 것을 확인하는 것은 간단하다.

또 다른 예로, 스도쿠 문제에서 답이 주어지면 스도쿠 규칙에 맞는지 쉽게 확인할 수 있지만, 일반적인 스도쿠 문제에서 답을 찾는 것은 NP에 속하지만 P에 속하는지는 아직 알려지지 않았다.

NP는 비결정적 튜링 머신을 사용하여 정의될 수 있다.^[8] 현대적인 접근 방식은 '증명서'와 '검증자'의 개념을 사용한다. 공식적으로, NP는 유한 알파벳과 다항 시간 내에 실행되는 검증자를 가진 언어의 집합으로 정의된다.

유한 알파벳 Σ에 대한 언어 ''L''이 있을 때, 다음 두 조건을 만족하는 이진 관계

R\subset\Sigma^{*}\times\Sigma^{*}

와 양의 정수 ''k''가 존재하면 ''L'' ∈ NP이다.

# 모든

x\in\Sigma^{*}

에 대해,

x\in L \Leftrightarrow\exists y\in\Sigma^{*}

such that (''x'', ''y'') ∈ ''R'' and

|y|\in O(|x|^k)

# 언어

L_{R} = \{ x\# y:(x,y)\in R\}

over

\Sigma\cup\{\#\}

는 결정적 튜링 머신에 의해 다항 시간 내에 결정 가능하다.

''L_R''을 결정하는 튜링 머신은 ''L''의 '검증자'라고 불리며, (''x'', ''y'') ∈ ''R''인 ''y''는 ''L''에 ''x''의 '멤버십 증명서'라고 불린다.

6. 해결 가능성에 대한 예상

2002년부터 미국의 컴퓨터 과학자 윌리엄 가사치(William Gasarch)는 P-NP 문제에 관한 설문을 세 차례 진행하였다.^[69]^[70] P ≠ NP일 것이라고 예상한 사람의 비율은 2002년에 61%, 2012년에 83%, 2019년에 88%로 점차 증가하였다. 전문가로 대상을 한정했을 때에는 P ≠ NP일 것이라고 답한 비율이 99%에 달했다.^[71]

많은 연구자가 P≠NP라고 예상하고 있지만, P=NP라고 예상하는 연구자도 일부 존재한다. 도널드 커누스는 P≠NP를 증명하려는 시도가 모두 실패했고, NP 문제를 풀기 위한 엄청나게 많은 종류의 알고리즘이 모두 실패한다고 믿기 어렵다는 점을 논거로 들었다.^[61] 그러나 그는 P=NP가 증명된다 하더라도 실용적으로 도움이 되지 않을 가능성이 높다고 덧붙였다.^[61]

7. P가 "쉬운" 것을 의미하는가?

코밤의 테제에 따르면 P가 "쉽다"는 것을 의미하고 "P에 속하지 않음"이 "어렵다"는 것을 의미한다. 이는 복잡도 이론에서 흔히 사용되는 가정이지만, 몇 가지 주의할 점이 있다.

첫째, 실제로는 틀릴 수 있다. 이론적인 다항식 시간 알고리즘은 매우 큰 상수 계수나 지수를 가질 수 있으며, 이는 실용성을 떨어뜨린다. 예를 들어, 그래프 ''G''에 ''H''가 그래프 마이너로 포함되어 있는지 여부를 결정 문제로 결정하는 문제는 ''O''(''n''²)의 실행 시간 안에 해결될 수 있다.^[25] 여기서 ''n''은 ''G''의 정점 수이다. 그러나 빅 오 표기법은 ''H''에 초지수적으로 의존하는 상수를 숨긴다. 그 상수는 $2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2) ) )$ 보다 크며(Knuth의 위쪽 화살표 표기법 사용), 여기서 ''h''는 ''H''의 정점 수이다.^[26]

반면에, 문제가 NP-완전 문제로 밝혀지고 P ≠ NP임에도 불구하고, 실제 문제에 효과적인 접근 방식이 여전히 있을 수 있다. 배낭 문제, 외판원 문제, 부울 만족 문제와 같은 많은 NP-완전 문제에 대한 알고리즘이 있으며, 이는 많은 실제 문제 사례를 합리적인 시간 안에 최적으로 해결할 수 있다. 이러한 알고리즘의 경험적인 평균 시간 복잡도(시간 vs. 문제 크기)는 놀랍도록 낮을 수 있다. 한 예로 선형 계획법의 심플렉스 알고리즘이 있는데, 최악의 경우 시간 복잡도가 지수 시간이 소요됨에도 불구하고 실제로는 놀랍도록 잘 작동하며, 가장 잘 알려진 다항 시간 알고리즘과 동등한 수준으로 실행된다.^[27]

마지막으로, P와 NP가 정의된 튜링 기계 모델에 부합하지 않는 계산 유형이 있으며, 예를 들어 양자 컴퓨터 및 랜덤 알고리즘이 있다.

8. 더 어려운 문제들

EXPTIME은 지수 시간 안에 결정적 튜링 기계로 풀 수 있는 모든 결정 문제의 집합이다. EXPTIME-완전은 EXPTIME에서 가장 어려운 문제들의 집합으로, EXPTIME의 모든 문제가 이 문제로 다항 시간 다대일 감소될 수 있다. P ≠ EXPTIME이므로, EXPTIME-완전 문제들은 P 밖에 있으며 다항 시간보다 더 많은 시간이 필요하다. 시간 계층 정리에 따르면, 이 문제들은 지수 시간보다 훨씬 적은 시간 안에 해결될 수 없다. ''N'' × ''N'' 체스판에서 체스 위치에 대한 완벽한 전략을 찾는 문제^[16]와 다른 보드 게임에 대한 유사한 문제^[17]가 그 예이다.

프레스버거 산술에서 명제의 참 거짓을 결정하는 문제는 더 많은 시간을 필요로 한다. 피셔와 라빈은 1974년에^[18] 길이 ''n''인 프레스버거 명제의 참 거짓을 결정하는 모든 알고리즘의 실행 시간이 어떤 상수 ''c''에 대해 최소 $2^{2^{cn}}$ 임을 증명했다. 따라서 이 문제는 지수 시간보다 더 많은 실행 시간이 필요한 것으로 알려져 있다. 정지 문제와 같은 결정 불가능한 문제는 어떤 알고리즘으로도 완전히 해결할 수 없다. 이는 특정 알고리즘에 대해 올바른 답을 생성하지 못하는 입력이 최소 하나 이상 존재함을 의미한다. 즉, 잘못된 답을 생성하거나, 결정적인 답을 제시하지 않고 종료되거나, 답을 생성하지 않고 영원히 실행될 것이다.

9. 다항 시간 알고리즘

NP-완전 문제에 대해 알려진 알고리즘은 다항 시간 내에 실행되지 않는다. 그러나 만약 P = NP라면, NP-완전 문제에 대한 알고리즘이 존재하며, 긍정적인 경우(accepting instances)에는 다항 시간 내에 실행된다. 다만, 이 알고리즘은 매우 큰 상수를 가질 수 있어 실용적이지 않을 수 있다.^[61] 이러한 알고리즘은 거부하는 경우(rejecting instances)에는 실행 시간이 다항식이 아니기 때문에 다항 시간으로 간주되지 않는다.

레빈이 제안한 알고리즘(인용 없음)은 이러한 예시 중 하나이다. 이 알고리즘은 NP-완전 언어인 SUBSET-SUM을 올바르게 수용한다. P = NP인 경우에만 SUBSET-SUM에 속하는 입력에 대해 다항 시간 내에 실행된다.

```

''// NP-완전 언어 SUBSET-SUM을 수용하는 알고리즘.''

''//''

''// P = NP인 경우에만 다항 시간 알고리즘임.''

''//''

''// "다항 시간"은 정답이 "yes"일 때 다항 시간 내에 "yes"를 반환하고, "no"일 때는 영원히 실행됨을 의미함.''

''//''

''// 입력: S = 정수의 유한 집합''

''// 출력: S의 어떤 부분 집합이 0으로 합산되면 "yes".''

''// 그렇지 않으면 출력이 없이 영원히 실행됨.''

''// 참고: "프로그램 번호 M"은''

''// 정수 M을 이진수로 쓰고, 그 비트 문자열을''

''// 프로그램으로 간주하여 얻은 프로그램입니다. 모든 가능한 프로그램은''

''// 이런 방식으로 생성될 수 있지만, 구문 오류로 인해 대부분 아무것도 하지 않습니다.''

FOR K = 1...∞

FOR M = 1...K

입력 S로 K단계 동안 프로그램 번호 M 실행

IF 프로그램이 서로 다른 정수 목록을 출력하는 경우

AND 정수가 모두 S에 있는 경우

AND 정수의 합이 0인 경우

THEN

"yes" 출력 및 HALT

```

이 알고리즘은 P = NP인 경우에만 NP-완전 언어를 수용하는 다항 시간 알고리즘이다. "수용"은 다항 시간 내에 "yes" 응답을 제공하지만, 응답이 "no"일 때는 영원히 실행될 수 있다 (''반-알고리즘''이라고도 함).

이 알고리즘은 P = NP인 경우에도 매우 실용적이지 않다. SUBSET-SUM을 다항 시간 내에 해결할 수 있는 가장 짧은 프로그램이 ''b'' 비트 길이인 경우, 위의 알고리즘은 먼저 2^''b'' − 1개 이상의 다른 프로그램을 시도한다.

도널드 커누스는 P = NP라고 예상하는 연구자 중 한 명이다. 그는 P ≠ NP를 증명하려는 시도가 모두 실패했고, NP 문제를 n^M 단계로 푸는 알고리즘에서 M이 10↑↑↑↑3과 같은 거대한 값을 가질 수 있다면, n 비트 입력에 대해 n^M개의 논리 연산 등을 실시하는 엄청난 종류의 알고리즘이 생각될 수 있으며, 이것이 모두 실패한다고는 믿기 어렵다고 주장한다.^[61] 그러나 그는 동시에 P = NP가 증명되더라도 비구성적 증명일 가능성이 높아 실용적이지 않을 것이라고 말했다.^[61]

10. 유사한 문제

R vs. RE 문제는 R이 클래스 P의 유사 클래스이고, RE가 클래스 NP의 유사 클래스인 문제이다. 힐베르트의 열 번째 문제와 같이 결정 불가능하지만 검증 가능한 문제가 존재하며, 이 문제는 RE-완비이기 때문에 이 두 클래스는 동일하지 않다.

대수적 복잡도 이론에도 VP vs. VNP와 유사한 문제가 존재한다. 이 문제는 아직 해결되지 않았다.^[59]^[60]

참조

_[1] 문서 nondeterministic Turing machine
_[2] 논문 The status of the P versus NP problem http://www.cs.uchica[...] 2010-01-26
_[3] 서적 The Golden Ticket: P, NP, and the Search for the Impossible Princeton University Press
_[4] 서적 Proceedings of the Third Annual ACM Symposium on Theory of Computing
_[5] 논문 http://www.mathnet.r[...] 1973
_[6] 웹사이트 Letters from John Nash https://www.nsa.gov/[...]
_[7] 논문 Gödel, von Neumann, and the P = NP problem http://ecommons.libr[...]
_[8] 문서 Introduction to the Theory of Computation, Second Edition, International Edition Thomson Course Technology
_[9] 논문 The P=?NP poll. http://www.cs.umd.ed[...] 2002-06
_[10] 논문 The Second P=?NP poll http://www.cs.umd.ed[...]
_[11] 웹사이트 Guest Column: The Third P =? NP Poll1 https://www.cs.umd.e[...] 2020-05-25
_[12] 웹사이트 PHYS771 Lecture 6: P, NP, and Friends http://www.scottaaro[...] 2007-08-27
_[13] 웹사이트 MSc course: Foundations of Computer Science http://www.cs.ox.ac.[...] 2020-05-25
_[14] 논문 The complexity of completing partial Latin squares
_[15] 논문 The NP-completeness of some edge-partition problems
_[16] 논문 Computing a perfect strategy for ''n'' × ''n'' chess requires time exponential in ''n''
_[17] 웹사이트 Computational Complexity of Games and Puzzles http://www.ics.uci.e[...]
_[18] 논문 Super-Exponential Complexity of Presburger Arithmetic http://www.lcs.mit.e[...] 2017-10-15
_[19] 논문 The complexity of enumeration and reliability problems
_[20] 논문 Graph isomorphism is in SPP
_[21] 논문 Graph isomorphism is in the low hierarchy
_[22] 간행물 Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures World Sci. Publ., Hackensack, NJ
_[23] 웹사이트 Complexity Class of the Week: Factoring http://weblog.fortno[...] 2002-09-13
_[24] 문서 "Where are the hard knapsack problems?" Department of Computer Science, University of Copenhagen, Copenhagen, Denmark
_[25] 논문 The disjoint paths problem in quadratic time
_[26] 논문 The NP-completeness column: An ongoing guide (edition 19)
_[27] 서적 Advances in linear and integer programming Oxford University Press
_[28] 논문 P vs. NP poll results http://mags.acm.org/[...] 2012-05
_[29] 웹사이트 Reasons to believe http://scottaaronson[...] 2006-09-04
_[30] 서적 Structural Complexity II Springer Verlag 1990
_[31] 문서 Exactly how efficient a solution must be to pose a threat to cryptography depends on the details. A solution of O(N^2) with a reasonable constant term would be disastrous. On the other hand, a solution that is Ω(N^4) in almost all cases would not pose an immediate practical danger.
_[32] 서적 Algorithms and Computation Springer
_[33] 논문 Logical cryptanalysis as a SAT problem
_[34] 간행물 Inversion attacks on secure hash functions using SAT solvers Springer
_[35] 논문 Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete
_[36] 웹사이트 The History and Status of the P versus NP question http://cs.stanford.e[...]
_[37] 서적 Optimization Stories https://www.academia[...] 2012-08
_[38] 웹사이트 The P versus NP Problem https://www.claymath[...] 2006-10-18
_[39] 서적 Twenty Questions for Donald Knuth http://www.informit.[...] InformIT 2014-07-20
_[40] 간행물 On the structure of polynomial time reducibility
_[41] 간행물 The Heuristic Problem-Solving Approach 1983-10
_[42] 문서 A personal view of average-case complexity http://cseweb.ucsd.e[...] 10th Annual Structure in Complexity Theory Conference (SCT'95) 1995
_[43] 웹사이트 Tentative program for the workshop on "Complexity and Cryptography: Status of Impagliazzo's Worlds" http://intractabilit[...]
_[44] 간행물 Relativizations of the P =? NP Question
_[45] 간행물 Natural proofs
_[46] 학회 Algebrization: A New Barrier in Complexity Theory http://www.scottaaro[...]
_[47] 웹사이트 Is P Versus NP Formally Independent? http://www.scottaaro[...]
_[48] 기술보고서 On the independence of P versus NP https://www.cs.techn[...]
_[49] 문서 P versus NP http://www.unizar.es[...] Monografías de la Real Academia de Ciencias de Zaragoza 2004
_[50] 간행물 PRIMES is in P http://www.cse.iitk.[...]
_[51] 뉴스 Prizes Aside, the P-NP Puzzler Has Consequences https://www.nytimes.[...] 2009-10-08
_[52] 웹사이트 The P-versus-NP page https://wscor.win.tu[...] 2018-06-24
_[53] 뉴스 Step 1: Post Elusive Proof. Step 2: Watch Fireworks. https://www.nytimes.[...] 2010-09-20
_[54] 매거진 'Travelling Salesman' movie considers the repercussions if P equals NP https://www.wired.co[...] 2012-04-26
_[55] 웹사이트 Explained: P vs. NP https://news.mit.edu[...] 2009-10-29
_[56] 웹사이트 What is the P vs. NP problem? Why is it important? http://science.nd.ed[...] 2013-09-13
_[57] 웹사이트 P vs NP is Elementary? No— P vs NP is ON Elementary https://blog.computa[...] 2018-07-06
_[58] 뉴스 Elementary Solve for X Review: Sines of Murder http://www.tv.com/ne[...] 2018-07-06
_[59] 문서 Completeness classes in algebra Proc. of 11th ACM STOC 1979
_[60] 서적 Mathematics and Computation: A Theory Revolutionizing Technology and Science Princeton University Press
_[61] 웹사이트 Twenty Questions for Donald Knuth http://www.informit.[...] InformIT 2017-06-10
_[62] 웹사이트 Letters from John Nash https://www.nsa.gov/[...] 2017-06-10
_[63] 간행물 Godel, von Neumann, and the P = NP problem https://doi.org/10.1[...]
_[64] 저널 The status of the P versus NP problem http://www.cs.uchica[...] 2022-12-04
_[65] 서적 The Golden Ticket: P, NP, and the Search for the Impossible https://archive.org/[...] Princeton University Press
_[66] 서적 Proceedings of the Third Annual ACM Symposium on Theory of Computing
_[67] 웹인용 Letters from John Nash https://www.nsa.gov/[...]
_[68] 저널 Gödel, von Neumann, and the P = NP problem http://ecommons.libr[...]
_[69] 저널 The P=?NP poll. http://www.cs.umd.ed[...] 2002-06
_[70] 저널 The Second P=?NP poll http://www.cs.umd.ed[...]
_[71] 웹인용 Guest Column: The Third P =? NP Poll1 https://www.cs.umd.e[...] 2022-12-06

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com