P-NP 문제: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
내용 수정및 추가 |
정직한 내용 |
||
1번째 줄:
{{밀레니엄 문제}}
[[파일:Complexity classes.png|섬네일|P는 NP에 속하지만, NP가 P에 속하는지 여부는
'''P-NP 문제'''는 [[복잡도 종류]] [[P (복잡도)|P]]와 [[NP (복잡도)|NP]]가 같은지에 대한 [[컴퓨터 과학]]의 미해결 문제로 컴퓨터로 풀이법이 빠르게 확인된 문제가 컴퓨터로 빠르게 풀리기도 할 것인가 아닌가를 묻고 있다. [[1971년]] [[스티븐 쿡]]이 그의 논문 〈The Complexity of Theorem Proving Procedures〉(정리 증명 절차의 복잡성)에서 처음으로 제안하였고 [[클레이 수학연구소]]에서 발표한 7개의 [[밀레니엄 문제]] 중 하나이며 컴퓨터 과학에서 중요한 위치를 차지하고 있다. 이것은 본래 1956년 [[쿠르트 괴델]]이 [[존 폰 노이만]]에게 썼던 편지에서 처음으로 언급되었다. 괴델은 어떤 NP 완전 문제가 2차 혹은 선형 시간 안에 풀릴 수 있는지 아닌지를 물었다.
P는 [[결정론적 튜링 기계]]를 사용해 [[다항 시간]] 내에 답을 구할 수 있는 문제의 집합이고, NP는 [[비결정론적 튜링 기계]]를 사용해 다항 시간 내에 답을 구할 수 있는 문제의 집합이다. 여기에서 결정론적 튜링 기계에 사용한 프로그램을 비결정론적 튜링 기계에 적용할 수 있으므로, P는 NP의 부분집합이 된다.
위에 사용된 일상적인 단어인 "빠르게"는 [[다항 시간]]안에 실행되는 작업을 위한 알고리즘의 존재를 의미한다. 다항시간 안에 답을 제공하는 알고리즘이 있는 문제들의 일반 류 general class(종합적인 모임)를 P류 혹은 [[P (복잡도)|P]]라고 한다. 어떤 문제들은 빠르게 답을 찾을 수 있는 방법이 알려져 있지 않지만 답이 무엇인지를 나타내는 정보가 제공된다면 답을 빠르게 확인하는 것이 가능하다. 다항 시간 안에 확인할 수 있는 문제류를 [[NP (복잡도)|NP]]라고 한다.
| |||