NP-난해

위키백과 ― 우리 모두의 백과사전.

NP-난해, NP-hard는 NP에 속하는 모든 판정 문제를 다항 시간에 다대일 환산할 수 있는 문제들의 집합이다. 이때 NP-난해 집합에 속하는 문제가 NP에도 속하면 NP-완전에 속한다. 즉, NP-완전은 NP와 NP-난해의 교집합이다.

만약 P-NP 문제가 P=NP로 풀린다면 P=NP=NP-완전이므로 P와 NP는 NP-난해의 부분집합이 되고, P≠NP인 경우는 P와 NP-난해는 서로소가 된다.

NP-난해 집합은 NP에 속하지는 않는다. NP에 속하지 않는 NP-난해 문제의 한 예로는 정지 문제가 있다.

[편집] 정의

수학적으로는 이렇게 정의한다.

언어

L

이 $\forall L^\prime\in \mathbf{NP}, L^\prime \leq_p L\!$ 이면

L

은 NP-난해이다.

[편집] 보기

NP-난해 문제에 들어가는 판정 문제 가운데 대표적인 예로 부분집합 합 문제(SUBSET-SUM)가 있다. 이 문제는 정수 집합이 하나 있을 때, 원소를 모두 더하면 0이 되는, 공집합이 아닌 부분집합이 있는지를 묻는 문제이다. 이 문제는 NP에 들어가므로 NP-완전도 된다.

NP-난해이지만 NP-완전은 아닌 판정 문제도 있다. 예를 들어 정지 문제가 있다. "한 프로그램이 있고, 그 프로그램에 대한 입력이 있을 때, 이 프로그램은 영원히 돌 것인가?" 하는 문제이다. 이것은 예/아니오를 묻는 질문이므로 판정 문제이다. 정지 문제가 NP-난해이지만 NP-완전은 아님을 증명하기는 쉽다. 충족 가능성 문제를 정지 문제로 환산할 수 있기 때문이다. 정지 문제를 튜링 기계로 바꾸면 된다. 이 기계는 입력으로 받은 식에 대한 모든 진리값을 할당하려고 하는데, 식을 만족하는 진리값을 발견하면 멈추고, 그렇지 못하면 무한 루프에 빠지도록 한다. 정지 문제가 NP에 들어가지 않는다는 것을 확인하기도 쉽다. 모든 NP 문제는 연산을 유한번 써서 판정할 수 있지만, 정지문제는 일반적으로 그렇지 않기 때문이다.

[편집] 다른 정의

이 문서는 편집 지침에 맞춰 다듬어야 합니다. 이 문서를 정리해 주세요.

NP-난해의 다른 정의는 다항 시간 다대일 환산을 다항 시간 튜링 환산으로 바꾼 것이다. 이 정의도 자주 쓰인다. 이렇게 정의한 NP-난해성은 판정 문제뿐만 아니라 함수 문제에 대해서도 형식화할 수 있다.

이런 관점에서 문제 H가 NP-난해라는 것은, H에 대한 신탁을 주는 신탁 기계를 써서 NP에 들어 있는 모든 판정 문제 L을 다항 시간에 풀 수 있다는 뜻이다. (공식적인 사고방식은 아닌데, 이러한 기계는 H를 푸는 함수를 호출해서 L을 다항 시간에 푸는 알고리즘으로 생각할 수 있다. 단, 함수 호출 시간은 한 단위 시간만 걸려야 한다.) NP-난해 문제를 푸는 다항 시간 알고리즘을 찾는다면, 모든 NP-쉬움 문제를 다항 시간에 풀 수 있고, 이는 곧 모든 NP문제를 다항 시간에 풀 수 있다는 말과 같다.

NP-난해성에 대한 정의가 이 글 첫머리에 나오는 정의(판정 문제인 경우)와 같은지 다른지는 아직 풀리지 않은 문제이다. NP-완전에서 이 문제를 더 자세히 다룬다.

NP-난해

위키백과 ― 우리 모두의 백과사전.

[편집] 정의

[편집] 보기

[편집] 다른 정의

보기

개인 도구

찾기

둘러보기

도구모음

다른 언어