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

내용 삭제됨 내용 추가됨
→‎참고 사항: 내용수정함
태그: m 모바일 웹
TedBot (토론 | 기여)
잔글 봇: 틀 이름 및 스타일 정리
4번째 줄:
'''P-NP 문제'''는 [[복잡도 종류]] [[P (복잡도)|P]]와 [[NP (복잡도)|NP]]가 같은지에 대한 [[컴퓨터 과학]]의 미해결 문제로 컴퓨터로 풀이법이 빠르게 확인된 문제가 컴퓨터로 빠르게 풀리기도 할 것인가 아닌가를 묻고 있다. [[1971년]] [[스티븐 쿡]]이 그의 논문 〈The Complexity of Theorem Proving Procedures〉(정리 증명 절차의 복잡성)에서 처음으로 제안하였고 [[클레이 수학연구소]]에서 발표한 7개의 '밀레니엄 문제' 중 하나이며 컴퓨터 과학에서 중요한 위치를 차지하고 있다. 이것은 본래 1956년 [[쿠르트 괴델]]이 [[존 폰 노이만]]에게 썼던 편지에서 처음으로 언급되었다. 괴델은 어떤 NP 완전 문제가 2차 혹은 선형 시간 안에 풀릴 수 있는지 아닌지를 물었다.
 
P는 [[결정론적 튜링 기계]]를 사용해 [[다항 시간]] 내에 답을 구할 수 있는 문제의 집합이고, NP는 [[비결정론적 튜링 기계]]를 사용해 다항 시간 내에 답을 구할 수 있는 문제의 집합이다. 여기에서 결정론적 튜링 기계에 사용한 프로그램을 비결정론적 튜링 기계에 적용할 수 있으므로, P는 NP의 부분집합이 된다.
 
더욱이 진부분 속(proper sublattice)이 됨은 2003년경에 세학자(미국의 남기봉교수,중국의 왕슈안홍교수,한국의 김양곤교수)에 의하여 밝혀졌다.
 
위에 사용된 일상적인 단어인 "빠르게"​는 [[다항 시간]]안에 실행되는 작업을 위한 알고리즘의 존재를 의미한다. 다항시간 안에 답을 제공하는 알고리즘이 있는 문제들의 일반 류 general class(종합적인 모임)를 P류 혹은 [[P (복잡도)|P]]라고 한다. 어떤 문제들은 빠르게 답을 찾을 수 있는 방법이 알려져 있지 않지만 답이 무엇인지를 나타내는 정보가 제공된다면 답을 빠르게 확인하는 것이 가능하다. 다항 시간 안에 확인할 수 있는 문제류를 [[NP (복잡도)|NP]]라고 한다.
 
P ≠ NP​인NP인 것으로 들어났기때문에, NP안에는 풀이법을 확인하는 것보다 답을 계산하는 게 더 어려운 문제들이 있다는 것을 의미할 것이다. : 그런 문제들은 다항시간 안에 풀 수는 없지만 다항시간 안에 답을 확인할 수는 있다.
 
컴퓨터 과학에서 이 문제의 중요성을 차치하더라도, 이 문제의 증명은 수학, 암호, 알고리즘 연구, 인공지능, 게임이론, 멀티미디어 프로세싱, 철학, 경제학등 다양한 분야에 엄청난 영향을 끼칠 것이다.