COMPUTERS AND INTRACABLITY

어떤 알고리즘이 효율적인지 비효율적인지 구분할 때, Polynomial time algorithms과 Exponential time algorithms로 나눌 수 있다.

Polynomial Time Algorithms

• 시간 복잡도가 ( n )에 대한 다항식 함수로 표현될 수 있는 알고리즘.

Exponential Time Algorithms

• 시간 복잡도가 ( n )에 대한 다항식 함수로 표현되지 않는 알고리즘.
• ( n^{\log n} )과 같이 일반적으로 지수 함수로 간주되지 않는 일부 비다항 시간 복잡도 함수도 포함된다.
• Exponential time algorithms은 ( n )의 크기가 커짐에 따라 시간 복잡도가 기하급수적으로 증가한다.

문제 해결의 "Well-Solved" 기준

• 보통 Polynomial time algorithms을 찾기 전까지는 해당 문제를 "well-solved"했다고 보지 않는다. 이를 Intractable이라고 부른다.
• 다만, Exponential time algorithms이 실제로 유용하게 사용되는 경우도 간혹 있지만, 이는 매우 드물다.
• Polynomial time algorithms이긴 하지만 (n^{100}) 또는 (10^{99}n^2)인 경우 실제로 빠르게 실행된다고 보기 어렵다. 하지만, 자연적으로 발생한 다항시간 내에 해결되는 문제들은 많아도 2차, 3차 항 이고 과도하게 큰 계수를 가지지 않는다.

입력 인코딩과 컴퓨터 성능

• 어떤 인코딩이 합리적인지는 알 수 없지만, 아래 두 가지 규칙을 준수하면 문제 해결 불가능 여부에는 영향을 미치지 않는다고 봐야한다.

1. 간결하며, 필요없는 정보나 심볼이 없어야한다.
2. 숫자는 이진수, 10진수, 8진수등 1이 아닌 고정된 기준으로 표현된다.

• 또한, 어떤 컴퓨터를 사용하냐에 따라 실행 속도가 달라질 수 있지만, 현실적인 컴퓨터 내에서는 Intractable 문제의 구분에 크게 영향을 미치지 않는다.

Intractable Problem의 정의

• Intractable problem은 두 가지 의미로 사용될 수 있습니다:
  1. 솔루션을 찾기 위해 Exponential time만큼의 시간이 필요할 정도로 어려운 문제
  2. 솔루션이 다항 함수 범위에서 표현될 수 없는 문제.
• 그러나 두 번째 경우는 우리가 추가 정보를 요청하는 형태이기에 현실적이지 않다. 따라서 첫 번째 경우, 즉 Exponential time으로 해결되는 문제에 집중한다.

Intractable 문제와 해결 가능성

• 모든 증명된 Intractable 문제는 Undecidable(어떤 알고리즘으로도 해결 불가능)하거나 Non-deterministically intractable(실제로는 존재하지 않는 병렬 컴퓨터로는 해결 가능) 문제이다.
• 다만, 대부분의 Intractable 문제는 사실 결정 가능하며, Nondeterministic computer를 통해 Polynomial time 안에 해결 가능할 수 있다.

NP, NP-Complete, NP-Hard에 대한 정의

• NP는 결정 문제(솔루션이 Yes or no인 문제)들로, Nondeterministic computer를 사용하여 Polynomial time 내에 해결이 가능하다.
  이때 Deterministic computer를 사용하여 Polynomial time 내에 해결가능 한 문제들(P)은 당연히 Nondeterministic computer 로도 해결 되므로 P는 NP의 부분 집합니다.
• NP-complete는 그 중에서 가장 어려운 문제를 말한다. 이유는 NP 문제는 NP-complete로 다항 시간 내에 변환될 수 있다. 따라서 NP-complete를 해결하면 모든 NP 문제도 해결할 수 있다. 때문에 NP-complete를 NP중에서 가장 어렵다고 볼 수 있는 것이다.
• NP-hard또한 어려운 문제들로 NP 문제들은 NP-hard로 다항 시간 내에 변환될 수 있다. 하지만 NP-complete과 다른 점은 결정 문제일 수도 있고 아닐 수도 있다. 때문에 NP 문제일 수도, 아닐 수도 있다.

즉, NP문제로 다항 시간 내에 변환되는 어려운 문제중에 결정 문제들은 NP-complete 이며, 결정문제이거나 아닌 것들은 NP-hard라고 하는 것이다. 때문에 모든 NP-complete는 NP-hard이다.