우선 계산 문제는 정말 다양하지만, 대표적으로 결정 문제, 탐색 문제, 최적화 문제가 있다.
| 결정 문제 (Decision) | 길이가 10 이하인 경로가 존재하는가? | Boolean |
| 탐색 문제 (Search) | 길이가 10 이하인 경로를 찾아라. | List |
| 최적화 문제 (Optimization) | 가장 짧은 경로를 찾아라. | List |
옛날의 연구자들은 이러한 계산 문제들이 얼마나 어려운지를 알고 싶어 했다(물론 지금도 그러하다). 하지만, 앞서 얘기한 문제들은 입력과 출력이 모두 제각각이라서 이를 분석하는 게 어려웠다. 이때 나온 해결 방법이 모든 문제들을 대응되는 결정 문제로 치환하는 것이다. 예를 들면, 탐색 문제는 원래 "길이가 10 이하인 경로를 찾아라."는 문제이고 답은 실제 길이가 10 이하인 경로 List를 반환한다. 이를 결정 문제로 치환하면, "길이가 10 이하인 경로가 존재하는가?"로 변한다. 그리고 이 결정 문제를 우리가 흔히 아는 컴퓨터로 다항 시간 내에 풀어내서 True 또는 False라는 답이 나왔다면 해당 결정 문제는 P(다항 시간)에 속하게 된다. 왜냐하면 우리가 흔히 아는 컴퓨터는 결정론적 계산 모델이기 때문이다(자세한 건 후술).
연구자들이 결정 문제로 바꿔서 풀고자 했던 이유는 다음과 같은 관계가 성립하기 때문이다.
\[ \text{Search}\in FP \implies \text{Decision}\in P \]
FP와 P를 아직 정확히 모르겠지만, 풀어서 설명하면 다항 시간에 탐색을 할 수 있다면, 그 탐색 문제를 결정 문제로 치환한 것도 다항 시간에 풀 수 있다(다항 시간으로 결정할 수 있다). 이번엔 대우를 취하면 다음과 같다.
\[ \ \text{Decision}\notin P \implies \text{Search}\notin FP \]
즉 우리는 결정 문제에서 해당 문제가 P가 아님을 증명한다면, 탐색 문제도 FP가 아님을 주장할 수 있다. 즉, 다항 시간내에 탐색하는 알고리즘은 존재하지 않는다.
왜 다음과 같은 명제가 성립하는지 증명해보자.
Definition 1. 탐색 문제
x는 입력 데이터, y는 우리가 찾고자 하는 해, 그리고 \(R(x, \hat{y})\)는 \(\hat{y}\)가 유효한 해라면 1을 출력하고 아니라면 0을 출력하는 함수라고 했을 때 ,탐색 문제는 다음과 같다:
\[ \text{Find }\hat{y}\text{ such that }R(x,\hat{y})=1 \]
해가 존재하지 않는다면, FAIL을 출력한다.
예를 들면, \(x + \hat{y} = 10\)이 되면서 음이 아닌 \(\hat{y}\)를 출력하는 문제로 볼 수 있다.
Definition 2. 결정 문제로 치환
예를 들면, \(x + \hat{y} = 10\)과 \(\hat{y}\geq 0\)을 만족하는 \(\hat{y}\)가 존재하는지를 묻는 문제로 볼 수 있다.
Proposition 1. 탐색 문제가 FP이면, 대응하는 결정 문제는 P이다.
탐색 문제가 다항시간에 해결 가능하면 대응하는 결정 문제도 다항시간에 해결 가능하다.
Proof. 탐색 문제가 FP가 되는 알고리즘 A가 있다고 가정하자.
그러면 결정 문제를 푸는 알고리즘 D를 다음과 같이 정의할 수 있다.
\[ D(x)= \begin{cases} \text{True} & A(x)\neq\text{FAIL}\\ \text{False} & A(x)=\text{FAIL} \end{cases} \]
\(A(x)\)가 다항 시간에 \(\hat{y}\) 또는 \(\mathrm{FAIL}\)을 출력한다고 가정했기 때문에 결정 알고리즘 \(D\)도 다항 시간에 계산된다. 결정 문제를 다항 시간 내에 푸는 알고리즘 \(D\)가 존재하므로 명제가 성립한다. \(\square\)
