NP - hard

계산 복잡도 이론 (Computational Complexity Theory) 에서는 NP-hard (Non-deterministic Polynomial-time hard) 는 결정문제의 부류를 언급하는 것으로서, NP 에서 모든 결정문제 L 에 대해 H 에 대한 polynomial-time many-one reduction 이 있는 모든 문제 H 를 포함한다 (NP-hard refers to the class of decision problems that contains all problems H such that for all decision problems L in NP there is a polynomial-time many-one reduction to H).

비공식적으로 이러한 부류는 적어도 NP 에서의 어떤 문제 만큼 어려운 결정문제를 포함하는 것으로 묘사될수 있다. 이러한 직관은 polynomial time 내에 이러한 문제 H 중 하나를 해결하는 알고리즘 A 를 찾을수 있다는 사실로 부터 알수있다. 그때 이러한 문제로부터 H 까지 환원시켜 수행하고 알고리즘 A 를 수행함으로써 NP 에서 모든 문제를 위한 polynomial time algorithm 을 만들수 있다 (Informally this class can be described as containing the decision problems that are at least as hard as any problem in NP. This intuition is supported by the fact that if we can find an algorithm A that solves one of these problems H in polynomial time then we can construct a polynomial time algorithm for every problem in NP by first executing the reduction from this problem to H and then executing the algorithm A).

언어 L 이 NP-complete 라고 가정하면,

1. L is in NP

2. ∀L' in NP, L' ≤ L

NP-Hard 는 언어 L 이 속성 2 는 만족시키지만, 속성 1 를 반드시 만족시키는 것은 아니라고 가정한다.

NP-hardness 의 표기는 복잡 부류 (complexity classes) P 와 NP 간의 관계에 대한 논의에서 중요한 역할을 한다. 또한 NP 와 NP-hard 의 교차점인 복잡 부류 NP-complete 를 정의하기 위해서도 사용된다. 따라서 NP-hard 부류는 NP-complete 이거나 더 어려운 문제 부류인 것으로서 이해될 수 있다.

NP-hard 라는 용어속의 NP 가 non-polynomial 인 것으로 생각하기 쉬우나 그것은 큰 오류다. 그것은 이러한 문제들을 다항식 시간 내에 푸는 알고리즘이 없는 것으로 대강 추측되는 것이지만, 이것은 지금까지 결코 증명되지 않았다.

NP-hard 의 예

NP-hard 의 한 예로서 결정문제 SUBSET-SUM 이 있다 : 즉 일련의 integers 가 주어지고, 그들중 어떤 비어있지 않은 부분집합도 zero 에 더하지 않는가? 그것은 yes/no 질문이며 NP-complete 인 것이다. (An example of an NP-hard problem is the decision problem SUBSET-SUM which is this: given a set of integers, does any non empty subset of them add up to zero? That is a yes/no question, and happens to be NP-complete.)

정지문제 와 같이, NP-hard 이지만 NP-complete 는 아닌 결정문제들이 또한 있다. 정지문제는 "어떤 프로그램과 입력이 주어졌을 때, 영원히 실행할 것인가?" 하는 문제이다. 그답은 yes/no 이며 따라서 결정문제이다. 정지문제가 NP-hard 이지만 NP-complete 가 아니라는 것을 증명하기는 쉽다. 예를들면 boolean satisfiability problem 은, 모든 진리값을 할당해봐서 공식을 만족하는 것을 찾을 때 정지하고 못찾으면 무한 루프를 돌게되는 튜링머신의 개념으로 변형시킴으로써, 정지문제로 환원 (reduce) 될 수 있다, 정지문제가 NP 에 속하지 않는다는 것을 알기는 쉽다. 왜냐하면 NP 에 속하는 모든 문제들은 결정가능하고 (decidable) 정지문제는 결정가능하지 않기 때문이다.

또다른 정의

가끔 사용되는 NP-hard 의 또다른 정의는 polynomial-time many-one reductions 대신에 polynomial-time Turing reductions을 사용한다. NP-hardness 의 이러한 표기는 단지 결정문제가 아니라 function problems 로서 형식화 될 수 있다.

이런 의미에서, 만일 NP 에 속하는 모든 결정문제가 문제 H 를 위한 oracle을 가진 oracle machine (oracle machine with an oracle for H) 에 의해 다항식 시간내에 풀릴 수 있다면 문제 H 는 NP-hard 이다. (비공식적으로, 문제 H 를 풀기위한 subroutine 을 호출하고, 그 호출이 단지 한 단계의 계산만을 수행한다면, 다항식 시간내에 L을 해결할 수 있는 알고리즘으로서의  machine 을 생각할 수 있다)

만일 NP-hard 문제를 위한 다항식 시간 알고리즘 (polynomial-time algorithm) 을 발견한다면, NP-easy 에 속하는 모든 문제와 정말로 NP 에 속하는 모든 문제들에 대한 polynomial-time algorithm을 가지게 된다.

NP-hardness 의 이러한 정의가 위에서 언급한 것과 같은지 여부는 아직도 논의중인 문제이며, 그것에 대한 더 자세한 정의는 NP-completeness에서 논의된다. ............ (Wikipedia : NP-hard)

example :

배낭문제 (Knapsack Problem)   순회판매원 문제 (Travelling Salesman Problem)   Linear programming   Nonlinear programming   Quadratic assignment problem

term :

계산이론 (Theory of Computation)   계산 복잡도 이론 (Computational Complexity Theory)   P and NP   NP-hard  NP-complete

sitel :

NP problem : 전북대 박순철 교수님 동영상 (★★★)

video :

Heuristics for NP-Hard Problems : Richard Karp : 2011/10/16

복잡성 이론 : 임백준 : 'NP-hard' 라고 불리는 문제들은 세일즈맨의 여행 문제처럼 모든 경우의 수를 전부 확인해보는 방법 이외에는 정확한 답을 구할 수 있는 뾰족한 수가 없는 문제들을 뜻한다. 어떤 문제가 NP 에 속하면서, 즉 다항식으로 표현될 수 있는지 여부가 알려지지 않았으면서 동시에 NP-hard 에 속한다면, 즉 '무식한 힘' 의 방법말고 다른 절묘한 알고리즘이 알려져 있지 않다면 그 문제는 'NP 완전 문제 (NP complete)' 라고 부른다. 휴, 정말 복잡하다.

컴퓨터 학자들과 프로그래머들은 대개 NP 완전 문제를 실용적인 관점에서 해결하기 위해서 진짜 정답을 찾기를 포기하는 대신 휠씬 적은 양의 계산을 통해서 정답에 가까운 값을 찾는데 만족한다. 이러한 알고리즘은 근사 알고리즘 (approximation algorithm) 혹은 발견적 알고리즘 (heuristic algorithm) 이라고 부른다. 앞서 말한 MST, 탐욕 알고리즘 (Greedy algorithm), 평면절단 방법등은 모두 이러한 알고리즘의 예인데, 실전 프로그래밍의 세계에서는 이러한 근사 알고리즘이 생각보다 많이 사용된다. 예를들어서 1 장에서 보았던 '이상한 공식' 도 구태여 말하자면 근사 알고리즘에 해당하는 셈이다.

이러한 NP 완전 문제에 속하는 문제는 많다. 비밀번호를 깨뜨리기 위한 해킹 과정도 말하자면 이러한 NP 완전 문제에 속한다고 볼 수 있다. 비밀번호를 찾아내기 위한 알고리즘으로는 세일즈맨의 여행 문제에서처럼 문자를 하나씩 대입해 보는 것 말고는 다른 뾰족한 방법이 없기 때문이다. 그렇지만 이렇게 문자를 대입하는 경우에 시도해봐야 하는 경우의 수가 너무나 많기 때문에 이러한 방식으로 비밀번호를 찾아내는 것은 현실적으로 어렵다. 그러나 이론과 현실 사이에는 항상 간극이 존재하기 마련이다. 이론적으로 보았을 때 비밀번호를 깨뜨리는 문제는 NP 완전 문제에 속하도록 되어 있지만 현실은 그렇지 않기 때문에 문제가 발생한다. 우리는 이러한 간극을 뒤에서 곧 확인하게 될 것이다.

된장국과 NP-hard

오래간만에 시장에서 파를 사다가 된장국을 끓였다. 역시 된장국에는 파가 들어가야 제맛이 난다. 물에다 된장 넣고, 간장 넣고, 파를 뜯어서 넣고 다른 것은 안 넣을 때가 제일 순수한 맛이 난다. 그런데 이런 간단한 된장국을 맛있게 만드는 것도 NP라는 것을 알 수 있다. 왜냐하면 가장 맛있는 된장국을 만들기 위한 물, 된장, 간장, 파의 비를 맞추어야 하는 문제는 sum of subset 문제보다는 어렵고, sum of subset은 NP-completeness이기 때문이다. 때문에 가장 맛있는 된장국을 끓일 수 있는 사람은 NP-hard를 푼 사람이다. 따라서 어떤 사람이 맛있는 된장국을 만들게 되기까지의 과정을 잘 관찰해서 complexity를 분석할 수 있다면 우리는 알고리즘의 난제를 풀 수 있는 것이다.
실제로 가장 맛있는 된장국은 dynamic programming, greedy method등으로는 끓일 수 없다. 그 이유를 살펴보자.
먼저 principal of optimality가 성립하는가를 살펴보면 성립하지 않는다. 왜냐하면 4가지 재료로 만든 가장 맛있는 된장국이 3가지 재료나 2가지 재료로 만든 가장 맛있는 된장국의 비율로부터 나오지 않기 때문이다.따라서 dynamic programming으로는 가장 맛있는 된장국을 만들 수 없다.
다음으로 greedy method로 만드는 된장국을 살펴보자. 만약 n개의 재료로 제일 맛있는 혼합비를 만들었다고 하자. 하지만 이 혼합비에 한개의 재료를 가장 맛있는 비율로 첨가한다고 해서 이 비율이 n+1개로 만들 수 있는 가장 맛있는 비율은 아니다. 따라서 greedy method로도 가장 맛있는 된장국을 만들 수 없다. 다시 말하자면 약간 역설적으로 들리겠지만, 맛을 보면서 그 때 그 때 조금씩 재료를 음식에 첨가하는 방식으로는 결코 최고로 맛있는 음식을 만들 수 없는 것이다.
결론적으로 우리는 음식을 맛있게 만드는 사람을 NP-hard문제의 최적해에 근접한 해를 구하는 사람으로서 존경하지 않을 수 없다.
...나는 오늘도 NP-hard의 최적해를 구하기 위해 물을 올린다.

테트리스 게임은 NP hard 문제

MIT 공과대학교 컴퓨터 공학과의 과학자들이 80년대에 인기를 끌었던 테트리스 게임에 대해서 "NP-하드(hard)" 문제라는 결론을 내렸다. "NP-하드"와 "NP-컴플리트(complete)", "P", "NP" 등의 문제는 컴퓨터 공학의 기본인 컴퓨터 이론과 알고리즘에서 가장 중요하게 생각되는 개념으로, "NP-하드"한 문제는 간단히 생각하면 풀기 어려운 문제라고 간주될 수 있다. 즉 테트리스 게임을 하면서 꼭 이길 수 있는 수를 두는 것은 매우 어렵고 시간이 오래 걸린다는 것이다.

러시아에서 처음 개발된 테트리스 게임은 플레이어가 직사각형 게임보드 내에서 위에서 쏟아져 내려오는 도형들을 원하는 만큼 회전시켜 차곡차곡 쌓는 방식으로 진행된다. 한번 완성된 한 줄의 도형들은 사라지기 때문에 빈 곳이 없도록 도형을 채우는 것이 중요하다. 만일 잘못 도형을 쌓다가 꼭대기에까지 닿게 되면 플레이어는 게임에 지게 된다.

MIT 학자들은 오프라인 버전의 테트리스를 통해서, 만일 천장에서 내려오는 도형의 수가 유한할 때 공백을 만들지 않고 도형들을 쌓아올리는 계산은 폴리노미얼(polynomial)하지 않다는 것을 보여줬다.

그러나 "NP-하드"라는 것은 이론적인 결론일 뿐, 컴퓨터가 테트리스 게임을 잘 하도록 프로그래밍하는 데에는 실질적으로 큰 문제가 없다. 실제로 닌텐도 사는 사람과 대결하는 테트리스 컴퓨터 프로그램에 인공 지능 기술을 이용해 좋은 성적을 내고 있는데, 이 경우 대결하고 있는 사람보다 좋은 수를 두면 될 뿐이고 반드시 최적의 해법을 구해야 할 필요는 없기 때문에 MIT의 이론적인 분석 결과와는 달리 짧은 시간에 좋은 해법이 계산될 수 있다.