14. Intractability

1. Introduction

 

우리는 앞서서 DFA(Deterministic Finite Automata)라는 기계를 배웠다. 이 기계는 매우 강력하여 수많은 계산을 위한 모델이 될 수 있다. DFA는 Tape와 Tape head를 가지는 추상화된 기계인데, Tape는 input을 저장하고, finite symbol들을 가지고 있다. Tape head는 Tape의 input을 하나씩 차례대로 읽어들인다.

 

그런데, 이보다 더 강력한 기계가 존재하는데 바로 Turing machine이다.

Turing machine의 Tape는 input을 저장할 뿐만아니라, output, intermediate result 또한 저장한다. finite symbol들을 가진다.

Tape head는 Tape의 input을 차례로 읽어들일 뿐만아니라, symbol의 쓰기가 가능하다.

Church-Turing thesis는 Turing machine에 대한 논제인데, 다음과 같다.

 

Turing machines can compute any function that can be computed by a physically harnessable process of the natural world.

 

자연세계에서 효과적으로 풀 수 있는 함수는 Turing machine으로 계산가능하다.

이와같이 Turing machine은 매우 간단하고 General한 추상적모델이기 때문에, 우리는 최소한 이 자연세계 내에서는 더 강력하고 더욱더 General한 machine을 찾을 필요가 없다. 

 

과거 수십년동안 수많은 계산 모델을 만들려는 시도가 있었지만, 결국에는 모두 동일한 것으로 판별되었기 때문에, 더 나은 기계를 찾는 것은 의미가 없어보인다.

 

그렇다면, 자연세계에서 효과적으로 풀 수 있는 함수란 무엇인가? 아마도 우리는 input에 대해 exponential이 아닌 polynomial time에 풀 수 있다면 실제적으로 효과적으로 풀 수 있는 것으로 볼 수 있을 것이다. 

 

어떤 문제를 polynomial time에 풀 수 없다면, 우리는 그 문제를 intractable (난제) 이라고 한다.

 

2. Search problem

 

 Search problem이란, 문제의 Instance가 주어졌을 때 solution을 찾는것이다.

한가지 요구사항은, 효과적으로 solution이 맞는지를 체크할 수 있어야 한다.

 

LSOLVE(Linear equation), LP(Linear inequalities), ILP(Linear inequalities), SAT(Boolean equation) 문제들은 모두 solution을 제시했을 때 polynomial time에 check가 가능하므로 효과적으로 체크하는 문제이다. 따라서, Search problem이라고 볼 수 있다.

 

3. P vs NP

 

NP란, 모든 search problem들을 말한다.

P란, poly-time에 해결가능한 search problem들을 말한다.

따라서, P ⊂ NP 이다.

 

우리가 앞서 배운 NFA(Nondeterministic finite automata)를 생각해보자. 이것은 매 step마다 가능한 상태의 집합을 보여준다. 즉, 우리는 solution이 어떤 집합이 될 것인지를 추측할 수 있다.

NP문제의 경우, 이러한 Nondeterministic Turing Machine으로 poly-time에 해결가능하다.

P문제의 경우, poly-time에 해결가능한 문제이므로 자연세계에서 효과적으로 풀 수 있는 함수를 이용한다는 뜻이다.

즉, Deterministic Turing Machine으로 poly-time에 해결가능하다는 의미이다(Extended Church-Turing thesis)

 

우리에게는 중요한 문제가 있다. P = NP 인가?

 

어쩌면 이것은 여러가지 자연의 법칙과 관련이 있어보인다.

창의성을 활용해 어떤 새로운 원리를 발견하는 것이, 그것을 확인하는 것과 같은 수준의 문제인가?

놀랍게도 그것은 밀레니엄 난제로 아직도 증명되지 않았다.

P = NP라면 분명 세상이 완전히 바뀔것이지만, P ≠ NP를 증명해도 우리는 우주에 대한 놀라운 통찰을 얻을 수 있을 것이다. 하지만 우리는 많은 자연세계에서의 관찰로 아마도 일치하지 않을 것이라고 추측한다.

 

4. Classifying problems

 

SAT(Satisfiability)문제를 생각해보자.

이것은 boolean equation으로, n개의 변수가 주어졌을 때, Brute-force방식을 이용했을 때 2^n의 실행시간이 걸린다.

우리는 아직까지 SAT을 poly-time에 풀 수 없다.즉, Intractable이다.

 

우리가 앞서배운, linear-time reduce를 일반화한 poly-time reduce는 다음과 같이 정의된다.

Problem X poly-time reduces to problem Y if X can be solved with :

1) Polynomial number of standard computational steps

2) Polynomial number of calls to Y

 

만약, SAT이 poly-time reduce로 problem Y로 Reduction가능하다면, SAT이 intractable이므로 Y도 intractable라고 결론지을 수 있다.

우리는 SAT을 poly-time reduce를 통해 수많은 문제로 reduction해왔다.

ILP, Hamilton path, 3-COLOR... 등이 그러한 것이다. 지금도 수 많은 문제들이 SAT에서 reduction이 되었지만, 그러한 문제들또한 여전히 poly-time에 풀리지 않고있다. 이렇게 수많은 문제들 중 하나도 poly-time에 풀리지 않고있다니! 정말 P = NP는 성립하지 않는 것처럼 추측할만하다.

 

5. NP-completeness

 

모든 NP 문제가 poly-time reduce로 하나의 NP problem으로 reduction될 수 있다면, 그것은 NP-complete이다.

놀랍게도 SAT 은 NP-complete이며, 전체 문제의 난이도를 결정하는, 가장 어려운 NP문제가 된다.

Non-deterministic Turing machine 표기는 SAT 표기로 변환될 수 있고, SAT을 우리가 푼다면, 우리는 어떤 NP문제도 해결할 수 있다. 다시 말하면, Poly-time algorithm for SAT iff P = NP