NP-난해
위키백과 ― 우리 모두의 백과사전.
- 더 친절한 설명이 필요하면 P-NP 문제를 보라.
계산 복잡도 이론에서 NP-난해(NP-hard)란 NP에 들어 있는 모든 판정 문제 L이 판정 문제 H로 다항 시간 다대일 환산될 수 있는 H로 이루어진 복잡도 종류이다. NP-난해인 문제 H가 NP에 들어 있으면 H를 NP-완전이라고 한다.
NP-난해는 적어도 NP에 들어 있는 모든 결정 문제만큼 어려운 문제들의 집합이라고도 할 수 있다. (이것은 공식적인 정의는 아니다.) NP-난해 문제 H를 다항 시간에 푸는 알고리즘 A를 찾을 수 있다면, NP에 들어 있는 어떤 문제라도 H로 환산한 다음 A를 돌리면 되기 때문이다.
공식적으로는 이렇게 정의한다. 언어 L이 
이면 L은 NP-난해이다. 그리고 L이 NP이기도 하면 L은 NP-완전이다.
NP-난해 개념은 P-NP 문제를 얘기할 때 중요한 역할을 한다. NP-난해는 NP-완전이거나 그것보다 어려운 문제 종류로 볼 수 있다.
수많은 사람들이 "NP-난해"에서 "NP"를 다항이 아닌 것(영어: non-polynomial)으로 잘못 해석한다. 실제로 "NP"는 비결정론적 다항 시간(영어: nondeterministic polynomial)의 약자이다. (비결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 문제를 의미한다.) 많은 사람들이 NP-난해 문제를 푸는 다항 시간 알고리즘은 없다고 믿기는 하지만, 아직 아무도 증명하지 못했다. 게다가 다항 복잡도 문제는 NP에 들어간다는 사실을 잊으면 안 된다. (물론, P와 NP가 다르다면 다항 복잡도 문제는 NP-난해일 수 없다.)
NP가 붙은 용어들은 혼동을 불러오는 경우가 많다. NP-난해 문제 중에는 사실 NP에 들어 있지 않은 문제도 있다. 이 복잡도 종류 이름에 '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-완전에서 이 문제를 더 자세히 다룬다.
| 주요 복잡도 종류 (더 보기) |
|---|
|
P | NP | co-NP | NP-C | co-NP-C | NP-난해 | UP | #P | #P-C | L | NL | NC | P-C | PSPACE | PSPACE-C |
