P-NP 문제: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 봇: 주석→각주 (위키백과:봇 편집 요청/2015년 2월#2015-02-16 J13의 요청) |
쉬운 설명 추가 |
||
5번째 줄:
P는 [[결정론적 튜링 기계]]를 사용해 [[다항 시간]] 내에 답을 구할 수 있는 문제의 집합이고, NP는 [[비결정론적 튜링 기계]]를 사용해 다항 시간 내에 답을 구할 수 있는 문제의 집합이다. 여기에서 결정론적 튜링 기계에 사용한 프로그램을 비결정론적 튜링 기계에 적용할 수 있으므로, P는 NP의 부분집합이 된다. 하지만 여기에서 P와 NP가 같은 집합인지, 아니면 P가 NP의 [[진부분집합]]인지는 아직 밝혀지지 않았다. 현재 2000년에 클레이 수학연구소가 100만 달러를 걸었다.
'''< 좀 더 쉬운 설명 >'''
</br>P 대 NP 문제는 컴퓨터 과학에서 아직 풀리지 않은 중요한 문제인데, 컴퓨터에 의해 풀이법이 빠르게 확인된 문제가 컴퓨터에 의해 빠르게 풀리기도 할 것인가 아닌가를 묻고 있다. 이것은 본래 1956년 쿠르트 괴델([https://en.wikipedia.org/wiki/Kurt_G%C3%B6del Kurt Gödel])이 존 폰 노이만( [https://en.wikipedia.org/wiki/John_von_Neumann John von Neumann])에게 썼던 편지에서 처음으로 언급되었다. 괴델은 어떤 NP 완전 문제가 2차 혹은 선형 시간 안에 풀릴 수 있는지 아닌지를 물었다. P 대 NP 문제의 엄밀한 진술은 1971년 스티픈 쿡([https://en.wikipedia.org/wiki/Stephen_Cook Stephen Cook])이 그의 독창적인 논문 "정리 증명 절차의 복잡성"("[http://dl.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=805047 The complexity of theorem proving procedures]")에서 소개하였는데, 그 분야에서 가장 중요한 공개된 문제로 여기고 있다. 클레이연구소에 의해 채택된 [https://en.wikipedia.org/wiki/Millennium_Prize_Problems 7개의 밀레니엄 프라이즈 문제]로, 가장 먼저 제시된 옳은 해법에 1백만 달러를 수여하기로 되어 있기도 하다.
위에 사용된 일상적인 단어인 "빠르게"는 다항시간([https://en.wikipedia.org/wiki/Time_complexity#Polynomial_time polynomial time])안에 실행되는 작업을 위한 알고리즘의 존재를 의미한다. 다항시간 안에 답을 제공하는 알고리즘이 있는 문제들의 일반 류 general class(종합적인 모임)를 P류 혹은 [https://en.wikipedia.org/wiki/P_(complexity) P]라고 한다. 어떤 문제들은 빠르게 답을 찾을 수 있는 방법이 알려져 있지 않지만 답이 무엇인지를 나타내는 정보가 제공된다면 답을 빠르게 확인하는 것이 가능하다. 다항시간(polynomial time)안에 확인할 수 있는 문제들의 류(모임)를 [[NP]]라고 한다.
쉽게 풀이법이 확인될 수 있는 문제이지만 답을 계산하기는 어려울 수 있는 문제의 한 예인, 부분집합의 합계 문제 ([https://en.wikipedia.org/wiki/Subset_sum_problem subset sum problem])를 고려해 보기로 한다. 어떤 정수의 집합이 주어졌을 때, 공집합이 아닌 부분집합의 합계가 0일 수 있을까요? 예를 들면 {−2, −3, 15, 14, 7, −10}의 부분집합 중 어떤 것은 합계가 0일까? 답은 그렇다 이다. 왜냐하면 부분집합 {−2, −3, −10, 15}의 합계가 0 이기 때문인데, 이것은 3회의 덧셈으로 빠르게 풀린다. 그런데도 그런 부분집합을 다항시간 안에 찾아내는 알고리즘은 알려져 있지 않다.그런데 만약 P = NP라면 [https://en.wikipedia.org/wiki/Time_complexity 지수시간](2<sup>''n''</sup>-n-1 회)안에 풀리는 이 문제를 다항시간에 풀 수 있는 알고리즘이 존재할 것이다. ; 이런 이유로 이 문제는 (빠르게 확인가능한)NP안에 있지만 반드시 (빠르게 풀 수 있는)P안에 있지는 않다.
P = NP문제의 답은, 부분집합의 합계 문제와 같이 지수시간 안에 답을 계산할 수 있는 문제들(= 다항시간안에 확인가능한 문제들)이 다항시간안에도 답을 계산할 수 있는지를 결정할 것이다. 만약 P ≠ NP인 것으로 드러난다면, NP안에는 풀이법을 확인하는 것보다 답을 계산하는 게 더 여려운 문제들이 있다는 것을 의미할 것이다. : 그것들은 다항시간 안에 풀 수 없지만(답을 계산 할 수 없지만) 다항시간 안에 확인할 수는(풀이법을 찾을 수는) 있다.
컴퓨터 과학에서 이 문제의 중요성을 차치하더라도, 이 문제의 증명은 수학, 암호, 알고리즘 연구, 인공지능, 게임이론, 멀티미디어 프로세싱, 철학, 경제학등 다양한 분야에 엄청난 영향을 끼칠 것이다.
== 예상 ==
| |||