2020년 5월 15일 (금) 12:37 판 편집 DaedanBot (토론 \| 기여) 장기인증된 사용자 12,320 편집 잔글 →‎top: 문단 정리, using AWB ← 이전 편집		2020년 7월 3일 (금) 23:45 판 편집 편집 취소 211.255.211.181 (토론) 내용을 수정함 태그: m 모바일 웹 다음 편집 →
4번째 줄: '''P-NP 문제'''는 [[복잡도 종류]] [[P (복잡도)\|P]]와 [[NP (복잡도)\|NP]]가 같은지에 대한 [[컴퓨터 과학]]의 미해결 문제로 컴퓨터로 풀이법이 빠르게 확인된 문제가 컴퓨터로 빠르게 풀리기도 할 것인가 아닌가를 묻고 있다. [[1971년]] [[스티븐 쿡]]이 그의 논문 〈The Complexity of Theorem Proving Procedures〉(정리 증명 절차의 복잡성)에서 처음으로 제안하였고 [[클레이 수학연구소]]에서 발표한 7개의 '밀레니엄 문제' 중 하나이며 컴퓨터 과학에서 중요한 위치를 차지하고 있다. 이것은 본래 1956년 [[쿠르트 괴델]]이 [[존 폰 노이만]]에게 썼던 편지에서 처음으로 언급되었다. 괴델은 어떤 NP 완전 문제가 2차 혹은 선형 시간 안에 풀릴 수 있는지 아닌지를 물었다. P는 [[결정론적 튜링 기계]]를 사용해 [[다항 시간]] 내에 답을 구할 수 있는 문제의 집합이고, NP는 [[비결정론적 튜링 기계]]를 사용해 다항 시간 내에 답을 구할 수 있는 문제의 집합이다. 여기에서 결정론적 튜링 기계에 사용한 프로그램을 비결정론적 튜링 기계에 적용할 수 있으므로, P는 NP의 부분집합이 된다. 하지만 여기에서 P와 NP가 같은 집합인지, 아니면 P가 NP의 [[진부분집합]]인지는 아직 밝혀지지 않았다. 현재 2000년에 클레이 수학연구소가 100만 달러를 걸었다. 더욱이 진부분 속(proper sublattice)이 됨은 2003년경에 세학자(미국의 남기봉교수,중국의 왕슈안홍교수,한국의 김양곤교수)에 의하여 밝혀졌다. 위에 사용된 일상적인 단어인 "빠르게"는 [[다항 시간]]안에 실행되는 작업을 위한 알고리즘의 존재를 의미한다. 다항시간 안에 답을 제공하는 알고리즘이 있는 문제들의 일반 류 general class(종합적인 모임)를 P류 혹은 [[P (복잡도)\|P]]라고 한다. 어떤 문제들은 빠르게 답을 찾을 수 있는 방법이 알려져 있지 않지만 답이 무엇인지를 나타내는 정보가 제공된다면 답을 빠르게 확인하는 것이 가능하다. 다항 시간 안에 확인할 수 있는 문제류를 [[NP (복잡도)\|NP]]라고 한다.▼ ▲위에 사용된 일상적인 단어인 "빠르게"는 [[다항 시간]]안에 실행되는 작업을 위한 알고리즘의 존재를 의미한다. 다항시간 안에 답을 제공하는 알고리즘이 있는 문제들의 일반 류 general class(종합적인 모임)를 P류 혹은 [[P (복잡도)\|P]]라고 한다. 어떤 문제들은 빠르게 답을 찾을 수 있는 방법이 알려져 있지 않지만 답이 무엇인지를 나타내는 정보가 제공된다면 답을 빠르게 확인하는 것이 가능하다. 다항 시간 안에 확인할 수 있는 문제류를 [[NP (복잡도)\|NP]]라고 한다. 쉽게 풀이법이 확인될 수 있는 문제이지만 답을 계산하기는 어려울 수 있는 문제의 한 예인 [[부분집합 합 문제]]를 예를 들어보면 다음과 같다. 어떤 정수의 집합이 주어졌을 때 공집합이 아닌 부분집합중 적어도 하나 이상의 부분집합의 합계가 0일 수 있는지, 예를 들면 {−2, −3, 15, 14, 7, −10}의 부분집합 중 어떤 것은 합계가 0일지 생각해보면 답은 그렇다이다. 왜냐하면 부분집합 {−2, −3, −10, 15}의 합계가 0 이기 때문인데, 이것은 3회의 덧셈으로 빠르게 풀린다. 그런데도 그런 부분집합을 다항시간 안에 찾아내는 알고리즘은 알려져 있지 않다. 그런데 만약 P = NP라면 [[시간 복잡도]](2<sup>''n''</sup>-n-1 회)안에 풀리는 이 문제를 다항시간에 풀 수 있는 알고리즘이 존재할 것이다. 이런 이유로 이 문제는 빠르게 확인가능한 NP안에 있지만 반드시 빠르게 풀 수 있는 P안에 있지는 않다. P = NP문제의 답은, 부분집합의 합계 문제와 같이 지수시간 안에 답을 계산할 수 있는 문제들이 다항시간안에도 답을 계산할 수 있는지를 결정할 것이다. 만약 P ≠ NP인 것으로 ~~드러난다면~~들어났기때문에, NP안에는 풀이법을 확인하는 것보다 답을 계산하는 게 더 어려운 문제들이 있다는 것을 의미할 것이다. : ~~그것들은~~그런 문제들은 다항시간 안에 풀 수수는 없지만 다항시간 안에 ~~풀이법을~~답을 찾을확인할 수는 있다. 컴퓨터 과학에서 이 문제의 중요성을 차치하더라도, 이 문제의 증명은 수학, 암호, 알고리즘 연구, 인공지능, 게임이론, 멀티미디어 프로세싱, 철학, 경제학등 다양한 분야에 엄청난 영향을 끼칠 것이다.

P-NP 문제: 두 판 사이의 차이