P-NP 문제: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 봇: 분류:큰_토막글_문서 참고하여 토막글 틀 정리 |
부분집합 문제를 설명하는 과정에서 부분집합 전체의 합이 0인지 부분집합들 각각의 합 중에 최소 하나 이상의 합이 0인지가 구별이 가지 않음. |
||
8번째 줄:
위에 사용된 일상적인 단어인 "빠르게"는 [[다항 시간]]안에 실행되는 작업을 위한 알고리즘의 존재를 의미한다. 다항시간 안에 답을 제공하는 알고리즘이 있는 문제들의 일반 류 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안에는 풀이법을 확인하는 것보다 답을 계산하는 게 더 여려운 문제들이 있다는 것을 의미할 것이다. : 그것들은 다항시간 안에 풀 수 없지만 다항시간 안에 풀이법을 찾을 수는 있다.
| |||