The tower of light

쉬운 문제와 어려운 문제

  어떠한 문제가 답을 하기 쉬운 문제이고, 어떠한 문제가 답을 하기 어려운 문제인가? 답을 구하는 데 걸리는
시간이 짧은 문제가 쉬운 문제이고, 그렇지 않은 문제는 어려운 문제이다. 주어진 문제를 푸는 알고리즘 즉,
Turing 기계가 얼마나 작동하는가가 시간을 정하는데, 그 시간이 짧다 또는 길다는 것은 개개의 문제마다 의미
있는 것은 아니고, 집단문제(mass problem)에 부여된 개념이다.  마치 2 곱하기 3 은 잘 셈하지만, 다른 곱하기는
셈하지 못하는 계산기는 계산기가 아니듯이, 알고리즘이란 특정한 문제만을 푸는 데 사용되는 것이 아니라 보편적인
문제를 해결하여야 한다.

P : Deterministic algorithm에 의해 Polynomial time안에 풀 수 있는 decision problem들의 집합

NP : Non-deterministic algorithm에 의해 Polynomial time안에 풀 수 있는 decision problem들의 집합
(또 다른 정의로는 Deterministic algorithm을 사용하여 그 해답을 검증하는데 Polynomial time시간이 걸리는
문제들의 집합)

Hard : 어떤 class의 모든 문제가 문제 R로 다항식 시간 변환될 수 있지만 R이 그 class에 속한다는 조건이
없다면 R은 그 class에 대한 hard인 문제이다. 어떤 class의 hard인 문제는 그 class에 속하는 어떤 문제보다
풀기 어렵거나 비슷한 정도로 풀기 어렵다.

Complete : 어떤 class에 속하는 모든 문제가 그 class에 속하는 어떤 문제 R로 다항식 시간 변환 가능하다면
그 문제 R은 complete 문제이다. 즉, 어떤 class의 complete인 문제는 그 class의 모든 문제를 대표할 수 있는
것으로서 complete인 문제는 그 class 중에서 가장 어려운 문제로 생각할 수 있다.

Definition of NP-completeness
❶ it is in NP
❷ it is NP-hard, i.e. every other problem in NP is reducible to it.