계산 복잡도 입문

형식 언어와 오토마타 : Peter Linz 저서, 장직현. 김응모. 엄영익. 한광록 공역, 사이텍미디어, 2001 (원서 : An Introduction to Formal Languages and Automata. 3rd ed, Jones and Bartlett. 2001), Page 361~374  

1. 계산의 효율성    

2. 튜링 기계와 복잡도

3. 언어군들과 복잡도 부류들    

4. 복잡도 부류 P 와 NP

알고리즘과 계산이론을 공부하는 데 있어서 이 개념들을 실제의 컴퓨터에 적용했을 때 실제로 무엇이 기대될 수 있는지에 대해서 알아보자. 우리는 특정 문제들에 대한 알고리즘의 존재 여부에 관해서 알 뿐만 아니라, 실제의 계산에 대하여 원칙적으로 문제가 해결될 수 있는지를 아는 것은 물론 상당히 효율적으로 수행될 수 있는 알고리즘을 구성할 수 있어야 한다. 효율적으로 해결될 수 있는 문제들을 풀기 쉬운(tractable) 문제라고 한다. "풀기 쉬운 문제"란 서술적인 용어로서 보다 정확한 의미가 주어질 것이다.

실제로 소프트웨어를 개발하는 데 있어서, 효율성은 여러 가지 측면으로 생각해 볼 수 있다. 때로는 우리는 처리 시간과 기억공간 등과 같은 컴퓨터 자원의 효율적인 사용에 관심을 갖는다. 다른 경우에는, 소프트웨어를 얼마나 빨리 만들어 낼 수 있는지, 얼마나 효율적으로 유지될 수 있는지, 또는 얼마나 신뢰성이 있는지에 더 관심을 가졌다. 여전히 다른 경우에, 우리는 사용자의 문제가 효율적으로 해결될 수 있는지를 강조할 수도 있다. 이 모든 것들은 어떤 추상적인 이론에 의하여 집성되기에는 너무 복잡하다. 우리가 할 수 있는 모든 것은 더욱 현실적인 문제들의 일부분에 초점을 맞추고 이들에 대한 적절한 추상적인 골격을 만드는 것이다. 지금까지 개발된 대부분의 결과들은 계산에 대한 공간과 시간의 효율성에 대해 말하고 있다. 이것들은 복잡도 이론(complexity theory) 의 중요한 주제가 된다. 복잡도 연구에 있어서 주요한 관심사는 계산에 필요로 하는 시간과 공간으로 측정되는 계산의 효율성이다. 우리는 이것들을 알고리즘의 시간-복잡도(time-complexity) 와 공간-복잡도(space-complexity) 라고 한다.

계산 복잡도 이론(computational complexity theory) 은 광범위한 주제이고 그 대부분은 이 책의 범위를 벗어난다. 그러나 간단하게 명시될 수 있고, 쉽게 이해될 수 있는, 그리고 언어와 계산이론의 성질들을 더 밝혀주는 몇 가지 결과들이 있다. 이 절에서는 몇 가지 복잡도에 관한 결과들의 개요를 제시하기로 한다. 대부분 증명들이 어렵기 때문에 적절한 참고문헌들을 제시하고 증명은 생략하기로 한다. 이 절에서의 우리의 의도는 주요 문제에 대한 맛(flavor)을 소개하고 우리가 언어와 오토마타에 대해서 알고 있는 것들과 어떤 관계가 있는지 살펴보는 것이다. 이런 이유에서 주제의 선택과 논의의 형식에 있어서 폭넓게 다루려 할 것이다.

여기서는 시간-복잡도에 관해서만 논의를 할 것이다. 공간-복잡도에 대한 비슷한 결과들이 있지만 시간-복잡도가 훨씬 접근하기가 쉽다. 

1. 계산의 효율성

구체적인 예를 가지고 시작하기로 한다. 주어진 1000개의 정수들의 리스트에 대하여, 우리는 그 정수들을 어떤 순서로, 말하자면 오름차순으로, 정렬하려고 한다. 정렬은 간단한 문제이지만 컴퓨터 과학에 있어서 아주 기본적인 문제이다. 만일 우리가 "이 작업은 하는 데 얼마나 오래 걸릴 것인가?" 하고 묻는다면, 우리는 여기에 대한 답을 하기 전에 보다 ;많은 정보가 필요하다는 것을 즉시 알게 될 것이다. 분명히 리스트에 있는 항들의 수가 얼마나 많은 시간이 걸릴 것인지에 중요한 역할을 하겠지만 다른 요인들도 있다. 우리가 어떤 컴퓨터를 사용하고 프로그램을 어떻게 작성했는지에 대해서 질문이 있을 수 있다. 또한 여러 가지의 정렬 방법이 있기 때문에 알고리즘의 선택이 중요하다. 걸리는 시간을 대략적으로라도 추측할 수 있기 전에 알아볼 필요가 있다고 생각해 볼 수 있는 것들이 아마도 약간 더 있을 것이다. 만일 우리가 정렬에 대한 일반적인 묘사만을 하려고 한다면, 이들 쟁점들의 대부분이 무시되어야 하고, 우리는 가장 기본적인 것들에 집중해야 한다.

계산 복잡도에 대한 논의를 위하여 우리는 다음과 같이 단순화하는 가정을 할 것이다.

• 우리의 공부를 위한 모델은 튜링 기계가 될 것이다. 사용될 튜링 기계의 정확한 형식은 아래에서 논의될 것이다.
• 문제의 크기는 n 으로 표기될 것이다. 정렬 문제에 있어서 n 은 명백히 리스트에 있는 항들의 수이다. 문제의 크기가 항상 쉽게 특징 지워지는 것은 아닐지라도 일반적으로 어떻게 해서든 양의 정수와 연관 지을 수 있다.
• 알고리즘을 분석하는데 있어서, 특별한 경우에 대한 알고리즘의 수행 능력에는 일반적인 동작보다는 관심이 덜 하다. 특히 문제의 크기가 증가하는 경우 알고리즘이 어떻게 행동하는지에 관심이 있다. 따라서 주요한 의문은 n 이 커짐에 따라 자원의 요구가 얼마나 빠르게 증가하는가 하는 것이다.

그러므로 직접적인 목표는 컴퓨터 모델로서 튜링 기계를 이용하여 문제의 필요로 하는 시간이 그 문제의 크기의 함수로서 특성을 나타내는 것이 될 것이다.

우선 우리는 튜링 기계에 대한 시간의 개념의 의미를 제시한다. 우리는 튜링 기계가 한 단위 시간에 하나의 이동을 한다고 생각한다. 따라서 한 계산에 의해 취해진 시간은 행해진 이동의 수이다. 언급한 바와 같이 문제의 크기에 따라 계산적으로 필요한 시간이 어떻게 증가하는지 공부하기로 한다. 보통 주어진 크기의 모든 문제들의 집합에는 어떤 편차가 있다. 여기서 우리가 관심이 있는 것은 오직 가장 많은 자원을 필요로 하는 최악의 경우이다. 계산이 시간-복잡도 T(n) 을 갖는다는 말은 크기가 n 인 문제에 대한 계산이 어떤 튜링 기계상에서 T(n) 번 이하의 이동을 하고 완료될 수 있다는 것을 의미한다.

특정 형태의 튜링 기계를 계산 모델로 정하고 난 후에야 우리는 명확한 프로그램을 작성하고 그리고 문제를 해결하는 데 초래된 단계들의 수를 계산함으로써 알고리즘을 분석할 수 있을 것이다. 그러나, 여러 가지 이유로, 이 방법은 그다지 유용하지 않다. 첫째, 수행된 연산들의 수는 프로그램의 작은 세부사항에 따라 달라질 수 있고 따라서 프로그래머에 강하게 좌우된다. 둘째, 실질적인 입장으로부터, 우리는 알고리즘이 실세계에서 어떻게 수행하는지가 관심이 있다. 그 결과는 그 알고리즘이 튜링 기계에서 수행하는 것과는 상당한 차이가 있을 수 있다. 우리가 기대할 수 있는 최상은 튜링 기계 분석이 실제 수행의 중요한 모습을, 예를 들면, 시간 복잡도의 점근적 증가율 (asymptotic growth rate) 을 나타내는 것이다. 그러므로 알고리즘이 필요로 하는 자원의 요구를 이해하는 첫 시도는 변함없이 크기-순위 (order-of-magnitude) 분석이다. 이 분석에서 우리는 O, θ 와 Ω 표기법을 사용한다. 이 접근방법의 분명한 비형식성 (informality) 에도 불구하고, 우리는 가끔 아주 유용한 정보를 얻는다.

 예제 1


주어진 n 개의 수들 x₁, x₂, ..., x_n 의 집합과 키 값 x 에 대하여, 집합이 x 를 포함하고 있는지를 결정하라.
집합이 어떤 방식으로 구성되어 있지 않다면, 가장 간단한 알고리즘은 일치되는 것을 찾든가 아니면 집합의 마지막 원소와 비교될 때까지 x 를 연속적으로 x₁, x₂, ...들과 비교하는 선형 탐색(linear search) 이다. 우리가 첫 번 비교에서 일치하는 것을 찾을 수도 있고 마지막 비교에서 일치하는 것을 찾을 수도 있기 때문에, 우리는 얼마만큼 작업을 할 것인지 예측할 수가 없다. 그러나 우리는, 최악의 경우에, n 번의 비교를 해야 한다는 것을 알고 있다. 우리는 이 선형 탐색의 시간 복잡도가 O(n) 이라고, 또는 더 정확하게, θ(n) 이라고 말할 수 있다. 이 분석을 하는 데 있어서, 우리는 이 알고리즘이 어느 기계에서 실행되는지 또는 이 알고리즘이 어떻게 구현되는지에 대하여 아무 특별한 가정을 하지 않았다.

2. 튜링 기계와 복잡도

여러 가지 형태의 튜링 기계들이 문제를 해결하는 능력에 있어서는 동치라는 것을 주장하였다. 이것은 논의를 위하여 가장 편리한 어떤 형식의 기계라도 선택할 수 있고 더욱이 표준 튜링 기계 모델을 사용하는 데 포함된 다소의 지루함을 피하기 위하여 고급 컴퓨터 언어들로 프로그램을 할 수도 있다. 그러나 복잡도에 관해서 생각할 때 여러 가지 튜링 기계들 사이의 동치성은 더 이상 유지되지 않는다.

 예제 2


다음 언어에 대한 단일-테이프 튜링 기계를 구성하였다.

L = { aⁿ bⁿ : n≥1 }

 

그림 1

이 알고리즘을 살펴보면 w = aⁿbⁿ 에 대하여 각각의 a 를 대응하는 b 와 매칭시키기 위하여 대강 2n 단계가 걸린다는 것을 알게 될 것이다. 그러므로 전체 계산 시간은 O(n²) 이다.
그러나 우리는 2-테이프 기계를 가지고 다른 알고리즘을 이용할 수 있다. 먼저 모든 a 를 두 번째 테이프에 복사하고, 그리고 난 후 각각의 a 를 첫 번째 테이프에 있는 b 에 매칭시킨다. 복사 전후의 상황들이 그림 1에서 보여진다. 복사와 매칭 모두 O(n) 시간 내에 행해질 수 있고 2-테이프 기계의 시간-복잡도는 O(n) 이다.

 예제 3


문맥-자유 언어에 대한 소속성 문제에서 , 입력 문자열 w 의 길이를 문제 크기 n 으로 한다면 철저한 탐색(exhaustive search) 방법은 복잡도 O(n^M) 을 갖는다. 여기서 M 은 문법에 따라 주어지는 값이다. 훨씬 효율적인 CYK 알고리즘은 O(n³) 의 복잡도를 갖는다. 이들 알고리즘 모두 결정적 알고리즘이다.
이 문제에 대한 비결정적 알고리즘은 단순히 w 의 유도에 어떤 생성규칙들이 순서대로 적용될 것인지를 추측함으로써 진행된다. 만일 단위-생성규칙이나 λ-생성규칙이 없는 문법으로 진행한다면 유도의 길이는 본질적으로 |w| 이고, 따라서 복잡도는 O(n) 이다.

 예제 4


여기서 복잡도 이론에 중요한 역할을 하는 만족성 문제(satisfiability problem)를 소개한다.

논리나 부울 상수 또는 변수는 참과 거짓으로 두 개의 값을 취할 수 있는 것이다. 우리는 각각 1 과 0 으로 표시할 것이다. 그리고 부울 상수나 변수들을 결합하여 부울식 (Boolean expression) 을 구성하기 위하여 부울 연산자가 사용된다. 가장 간단한 부울 연산자는 ∨ 로 표시되는 or 연산자와 ∧ 로 표시되는 and 연산자이고 다음과 같이 정의된다.

or 연산자 :

0∨1 = 1∨0 = 1∨1 = 1
0∨0 = 0

and 연산자 :

0∧0 = 0∧1 = 1∧0 = 0
1∧1 = 1

또한 부정도 필요하며 bar(^-) 로 표시하고 다음과 같이 정의된다.

논리곱 정규형 (conjunction normal form) 인 부울식을 생각해 보자. 이 정규형인 변수들 x₁, x₂, ..., x_n 에 대한 식은 다음과 같은 식으로부터 시작한다.

e = t_i ∧ t_j ∧ ... ∧t_{k                                                 (1)}

항 t_i, t_j, ..., t_k  들은 변수들과 변수들의 부정들을 or 연산하여 생성된다. 즉, 다음과 같다.

t_i = s_l ∨ s_m ∨ ... ∨ s_{p                                             (2)}

여기서 각 s_l, s_m, ..., s_p 는 변수이거나 변수의 부정을 나타낸다.

그리고 나서 만족성 문제는 다음과 같이 간단히 언급된다 : 논리곱 정규형으로 주어진 식 e 에 대하여, e 의 값이 참이 되도록 변수 x₁, x₂, ..., x_n 들에 값을 배정할 수 있는가? 특별한 경우로 다음 식을 살펴보기로 한다.



x₁=0 , x₂=1 , x₃=1 인 배정은 e₁ 을 참으로 만들기 때문에 이 식은 만족가능(satisfiable) 하다. 반면에,



은 변수들 x₁ 과 x₂ 에 대한 모든 배정이 e₂ 를 거짓으로 만들기 때문에 e₂ 는 만족가능하지 않다. 만족성 문제에 대한 결정적 알고리즘은 쉽게 발견할 수 있다. 변수들 x₁, x₂, ..., x_n 에 대한 모든 가능한 값들을 택하고 수식의 값을 계산한다. 그러한 선택들이 2ⁿ 개 있기 때문에 철저한 탐색은 지수적인 시간 복잡도(exponential time complexity) 를 갖는다.

비결정적인 접근방법 또한 문제를 간단하게 만든다. 만일 e 가 만족가능하다면 x_i 의 값을 추측한 후에 e 의 값을 계산한다. 이것은 본질적으로 O(n) 알고리즘이다. 예제 3 과 같이 복잡도가 지수적인 결정적 철저한 탐색 알고리즘과 선형 시간 비결정적 알고리즘을 얻을 수 있다. 그러나 앞의 예제와는 달리 이 문제에 대한 비지수적인 (nonexponential) 어떤 결정적 알고리즘도 알려져 있지 않고 있다.

이 예제들은 복잡도 문제는 우리가 사용하는 튜링 기계에 의하여 영향을 받고 결정성과 비결정성의 논의는 특히 중요한 것임을 제시하고 있다. 예제 2 에서는 다중테이프 기계에 대한 알고리즘이 컴퓨터 언어로 프로그램을 작성할 때 우리가 사용하는 것과 아주 가깝다는 것을 보여준다. 이 때문에 우리는 복잡도에 대한 문제들을 공부하기 위한 모델로서 다중테이프 튜링 기계를 사용할 것이다. 

3. 언어군들과 복잡도 부류들

언어분류에 대한 Chomsky 의 계층에서는 언어군들을 임시 기억장치의 성질에 의해 정의되는 오토마타의 부류와 연관을 시켰다. 언어를 분류하는 또 다른 방법은 특별한 형태의 튜링 기계를 사용하는 것이다. 그러나 이 방법은 시간 복잡도를 구별하는 요소로 생각한다.

 정의 1


만일 |w| ≤ n 인 L 에 속하는 모든 문자열 w 가 O(T(n)) 이동 내에서 승인된다면 튜링 기계는 T(n) 시간 내에 언어 L 을 인식한다고 말한다. 만일 M 이 비결정적이라면 이것은 모든 w ∈ L 에 대하여 승인에 이르게 되는 길이가 O(T(|w|)) 인 이동들의 순서열이 적어도 하나가 존재한다는 것을 의미한다.

 정의 2


만일 T(n) 시간 내에 L 을 인식하는 결정적인 다중테이프의 튜링 기계가 존재한다면 언어 L 은 부류 DTIME(T(n)) 에 속한다고 말한다.
만일 T(n) 시간 내에 L 을 인식하는 비결정적인 다중테이프의 튜링 기계가 존재한다면 언어 L 은 부류 NTIME(T(n)) 에 속한다고 말한다.

이들 복잡도 부류들 사이의 다음과 같은 관계들

DTMIE(T(n)) ⊆ NTIME(T(n))

그리고

T₁(n) = O(T₂(n))

이

DTIME(T₁(n)) ⊆ DTIME(T₂(n))

의미하는 것은 명백하지만, 이로부터 그 상황은 아주 불분명하게 된다. 우리가 말할 수 있는 것은 T(n) 의 차수가 증가함에 따라 점진적으로 보다 많은 언어들이 포함된다는 것이다.

 정리 1


k ≥ 1 인 모든 정수에 대하여

DTIME(n^k) ⊂ DTIME(n^k+1)

증명 : 이 증명은 Hopcroft 와 Ullman(1979, p.299)의 결과에 따른다.

이 정리로부터 이끌어 낼 수 있는 결과는 n² 시간 내에서 인식될 수 있지만 선형-시간 소속성 알고리즘이 존재하지 않는 어떤 언어들이 존재하고 그리고 DTIME(n²) 에는 속하지 않지만 DTIME(n³) 에 속하는 언어들이 존재하고, 그리고 등등이라는 것이다. 이 정리는 우리에게 무한 개의 중첩된 복잡도 부류들을 제시한다. 만일 지수적 시간 복잡도를 허용한다면 훨씬 더 많은 부류들을 얻을 수 있다. 사실 여기에는 한계가 없고 복잡도 함수 T(n) 이 얼마나 빠르게 증가하든 항상 DTIME(T(n)) 의 밖에 또 다른 것이 존재한다.

 정리 2

모든 순환적인 언어가 DTIME(f(n)) 에 속하게 되는 전체 튜링 계산가능 함수(total Turing computable function) f(n) 은 존재하지 않는다.

증명 : 알파벳 Σ = {0, 1} 을 생각해 보자. 그리고 Σ⁺ 에 속한 모든 문자열들이 고유 순서 w₁, w₂, ... 로 정렬되어 있다 하자. 그리고 M₁, M₂, ... 과 같은 튜링 기계들에 대한 고유 순서를 가정한다.
정리의 함수 f(n) 이 존재한다고 가정하자. 그러면 우리는 다음과 같은 언어 L 을 정의할 수 있다.

L = {w_i : M_i 는 f(|w_i| 단계 내에 w_i 를 인식할 수 없다.}                    (3)

우리는 언어 L 이 순환적인 언어라고 주장한다. 이것을 보이기 위하여 임의의 w ∈ L 을 생각하고 먼저 f(|w|) 를 계산한다. f 를 전체 튜링 계산가능 함수라고 가정함으로써 이것이 가능하게 된다. 그 다음 우리는 순서열 w₁, w₂, ...에서 w 의 위치 i 를 찾는다. 이것 또한 그 순서열이 고유 순서로 되어 있기 때문에 가능하다. 우리가 i 를 갖게 되면, M_i 를 찾아 이것을 f(|w|) 단계 동안 w 에 대해 작동시킨다. 이것으로부터 w 가 L 에 속하는지 여부를 말할 수 있고 따라서 L 은 순환적인 언어이다.
그러나 여기에서 우리는 L 이 DTIME(f(n)) 에 속하지 않는다는 것을 보일 수 있다. L 이 DTIME(f(n)) 에 속한다고 가정하자. L 이 순환적인 언어이기 때문에 L = L(M_k) 인 어떤 M_k가 존재한다. w_k 가 L 에 속하는가? 만일 w_k 가 L 에 속한다고 한다면 M_k 는 f(|w_k|) 단계 내에 w_k를 승인한다. L ∈ DTIME(f(n)) 이고 w ∈ L 인 모든 w 가 f(|w_k|) 내에서 M_k 에 의하여 승인되기 때문에 이것은 가능하다. 그러나 이것은 식 (3)에 모순이 된다. 반대로 만일 w_k ∉ L 이라고 가정한다면 또한 모순에 이르게 된다. 이와 같은 쟁점사항을 해결할 수 없음은 전형적인 대각선화의 결과이고 계산가능 함수 f(n) 이 존재한다는 원래의 가설은 반드시 거짓이 되어야 한다는 결론에 이르게 된다.

정리 1 과 2 는 여러 가지 주장들을 할 수 있도록 해준다. 예를 들면, DTIME(n³) 에 속하지 않지만 DTIME(n⁴) 에 속하는 언어가 있다. 비록 이것은 이론적으로는 흥미가 있다고 할지라도 그와 같은 결과가 실제적으로 중요한 의미가 있는지는 명확하지 않다. 이와 같은 관점에서 DTIME(n⁴)에 속하는 언어들의 특성이 무엇인지 실마리를 잡을 수 없다. 복잡도의 분류를 Chomsky 언어 계층과 연관시킨다면 그 문제를 약간 더 간파할 수 있다. 훨씬 명확한 결과를 제시하는 몇 가지 간단한 예제들을 살펴보기로 한다.

 예제 5


모든 정규 언어는 결정적 유한 오토마타에 의하여 입력의 길이에 비례하는 시간 내에 인식될 수 있다. 그러므로 다음 결과가 성립한다.

L_REG ⊆ DTIME(n)    

그러나 DTIME(n) 은 L_REG 보다 더 많은 언어를 포함한다. 문맥-자유 언어 {aⁿbⁿ : n ≥ 0}이 O(n) 시간 내에서 인식될 수 있다는 것을 알았다. 거기서 주어진 논의는 보다 복잡한 언어들에 대해서도 이용될 수 있다.

 예제 6


문맥-자유가 아닌 언어 L = {ww : w ∈ {a, b}^*} 는 NTIME(n) 에 속한다. 다음과 같은 알고리즘에 따라 이 언어에 해당하는 문자열들을 인식할 수 있기 때문에 이것은 쉽게 알 수 있다.

• 입력 파일로부터 입력을 테이프 1에 복사한다. 비결정적으로 이 테이프의 중간을 예측한다.
• 두 번째 부분을 테이프 2 에 복사한다.
• 테이프 1 의 심볼과 테이프 2 의 심볼을 하나씩 비교한다.

확실히 모든 단계들이 O(|w|) 시간 내에서 수행될 수 있다. 따라서 L∈ NTIME(n) 이다.
실제로, 만일 우리가 O(n) 시간 내에 문자열의 중간을 찾아내는 알고리즘을 고안할 수 있다면 L ∈ DTIME(n) 이라는 것을 보일 수 있다. 이것은 이루어질 수 있다. 테이프 2상에서 그 수를 계산하면서 테이프 1 에 있는 각각의 심볼을 살펴본다. 우리는 단지 각각의 두 번째 심볼만을 계산한다.

 예제 7


예제 3 으로부터 다음과 같은 결과가 나온다.

L_CF ⊆ DTIME(n³)
L_CF ⊆ NTIME(n)

문맥-인식 언어군을 생각하자. 여기서 철저한 탐색 파싱이 가능하다. 왜냐하면 매 단계마다 단지 제한된 수의 생성규칙들만이 적용 가능하기 때문이다. 그러므로 길이 n 인 모든 문자열은 n^M 시간 내에 파싱될 수 있다. 여기서 M 은 문법에 따라 정해지는 수이다. 그러나 이로부터 다음이 성립한다고 주장할 수 없다는 것을 알아야 한다.

L_CS ⊆ DTIME(n^M)

그 이유는 M 에 대한 상위 한계(upper bound) 를 설정할 수 없기 때문이다.

이 예제들로부터 T(n) 이 증가함에 따라 더욱더 많은 언어군들인 L_REG, L_CF, L_CS 등이 포함된다는 것을 유의하라. 그러나 Chomsky 의 계층과 복잡도 부류들 사이의 연결은 미약하고 명확치 않다.  

4. 복잡도 부류 P 와 NP

다른 성장률을 갖는 시간-복잡도를 통하여 의미있는 계층을 생성하려는 시도는 비생산적인 것으로 보여지기 때문에 덜 중요한 요소들을 무시하기로 한다. 예를 들면, DTIME(n^k) 와 DTIME(n^k+1) 과 같이 다소 흥미 없는 구별들을 제거하는 것들이 여기에 해당한다. 우리는 DTIME(n) 과 DTIME(n²) 과 같은 차이는 근본적인 것이 아니라고 주장할 수 있다. 그 이유는 그 차이의 일부는 우리가 가지고 있는 튜링 기계의 특별한 모델에(예를 들면, 테이프를 몇 개 가지고 있는가 등) 의존되고, 또한 어떤 모델이 실제 컴퓨터에 가장 적합한지 명확하지 않기 때문이다. 이것은 우리로 하여금 다음과 같은 유명한 복잡도 부류를 고려하도록 한다.

P

이 부류는 다항식의 차수에 관계없이 다항식 시간 내에 어떤 결정적 기계에 의하여 인식되는 모든 언어들을 포함한다. 이미 살펴본 바와 같이 L_REG 와 L_CF 는 P 에 속한다.
결정적 복잡도 부류들과 비결정적 복잡도 부류들 사이의 구별은 기본적인 것으로 보여지기 때문에 다음과 같은 NP 를 도입한다.

NP

명백히 P ⊆ NP 이지만 P 가 NP 의 진부분 집합인지는 알려지지 않고 있다. 일반적으로 P 에 속하지 않지만 NP 에는 속하는 어떤 언어가 있다고 여겨지고는 있지만 어느 누구도 아직 이와 같은 예를 발견하지 못했다.

이들 복잡도 부류, 특히 부류 P 에서 흥미있는 것은 현실적인 계산과 비현실적인 계산들을 구별하려는 시도로부터 발생한다. 비록 어떤 계산이 이론적으로는 가능하다고 할지라도 너무 많은 자원을 요구하기 때문에 이제까지 설계된 수퍼 컴퓨터는 물론, 현존하는 컴퓨터 상에서는 비현실적인 것으로 거부되어야 하는 것이 있다. 이와 같은 문제들은 원칙적으로는 계산가능하지만 실제적인 알고리즘에 대한 현실적인 기대를 할 수 없는 풀기 어려운 (intractable) 문제라고 한다. 이것을 보다 잘 이해하기 위하여 컴퓨터 과학자들은 형식적인 기반에 난해성(intractability)에 대한 개념을 올려 놓으려는 시도를 해왔다. 풀기 어려운 문제에 대한 용어를 정의하려는 시도로서 이른바 Cook-Karp 명제가 제시되었다. Cook-Karp 명제에서 P 에 속하는 문제는 풀기 쉬운 문제이고, P 에 속하지 않는 문제는 풀기 어려운 문제라고 한다.

이와 같은 Cook-Karp 명제가 현실적으로 우리가 해결할 수 있는 문제와 해결할 수 없는 문제를 분리하는 좋은 방법인가? 그 해답은 명확하지 않다. 확실하게 P 에 속하지 않는 어떤 계산은 다항식보다 더 빠르게 커지는 시간 복잡도를 갖고, 계산에 필요한 시간이 문제의 크기에 따라 훨씬 빨리 증가할 것이다. 2^0.1n 과 같은 함수에서조차도 n ≥ 1000 과 같이 큰 n 에 대하여 이 함수는 엄청나게 커질 것이고 아마도 이와 같은 복잡도를 갖는 문제를 풀기 어려운 문제라고 말해도 타당할 것이다. 그러나 DTIME(n¹⁰⁰) 에 속하는 문제에 대해서는 어떻게 될 것인가? Cook-Karp 명제에서는 그와 같은 문제를 풀기 쉬운 문제라고 하지만 작은 n 에 대해서도 그것을 확실하게 해결할 수 없다. Cook_Karp 명제에 대한 정당성은 P 에 속하는 대부분의 문제들이 DTIME(n), DTIME(n²), DTIME(n³) 에 속하고, 반면에 이 부류밖에 있는 문제들은 지수적인 복잡도를 갖는 경향이 있다는 실험적인 관측에 따른 것으로 보여진다. 실제 문제들 중에는 P 에 속하는 문제들과 P 에 속하지 않는 문제들 사이에 분명한 구별이 존재한다.

복잡도 부류들 P 와 NP 사이의 관계에 대한 연구는 컴퓨터 과학자들에게 특별한 관심을 불러일으켜 왔다. 이와 같은 문제의 근본은 P = NP 가 성립하느냐 성립하지 않느냐 하는 질문에 있다.

이것은 계산 이론에서 기본적인 미해결 문제 중의 하나이다. 이것을 탐구하기 위해 컴퓨터 과학자들이 다양한 관련된 개념들과 질문들을 도입하였다. 그들 중의 하나가 NP-complete 문제이다. 대충 말하자면 NP-complete 문제는 임의의 NP 문제만큼 어렵고, 또 어떤 의미에서는 모든 NP 문제들과 동치라는 것이다. 이것이 의미하는 바를 설명해야 한다.

 정의 3


언어 L₁ 의 알파벳에 대한 문자열 w₁ 이 w₁ ∈ L₁ 이고 오직 그럴 때에만 w₂ ∈ L₂ 이 되도록 언어 L₂ 의 알파벳에 대한 문자열 w₂ 로 다항식 시간 내에 변화시킬 수 있는 결정적 튜링 기계가 존재한다면, 이 언어 L₁ 이 L₂ 로 다항식-시간 변환가능(polynomial-time reducible) 하다고 말한다.

이 정의로부터 만일 L₁ 이 L₂ 로 다항식-시간 변환가능하고 또한 L₂ ∈ P 라면 L₁ ∈ P 라는 것을 알 수 있고, 마찬가지로 만일 L₂ ∈ NP 라는 것을 알 수 있다.

 정의 4


만일 L ∈ NP 이고 L' ∈ NP 인 모든 L' 이 L 로 다항식-시간 변환가능하다면 이 언어 L 은 NP-complete 라고 말한다.

이들 정의로부터 만일 어떤 L₁ 이 NP-complete 이고 L₂ 로 다항식-시간 변환가능하다면 L₂ 가 또한 NP-complete 가 된다는 것을 쉽게 알 수 있다. 이 정의가 의미하는 것은 만일 우리가 어떤 NP-complete 언어에 대한 결정적 다항식-시간 알고리즘을 발견할 수 있다면 NP 에 속하는 모든 언어는 P 에도 속한다는 것이다. 즉,

P = NP

가 성립한다는 것이다. 이 정의는 NP-completeness 를 질문에 대한 연구적 중심에 위치하게 하고 있다.

 예제 8


만족성 문제는 언어 문제로 간주될 수 있다. 특정 사례(instance)들을 수식이 만족가능하고 오직 그럴 때에만 승인되는 문자열로 부호화한다. 이 문제는 NP-complete 이다. 만족성 문제가 NP-complete 라는 것은 Cook 의 정리로 알려져 있고, 이 정리의 논의는 Hopcroft 와 Ullman(1979) 의 책에서 찾아볼 수 있다.

만족성 문제 이외에도 다른 많은 NP-complete 문제들이 발견되어 왔다. 그 문제들 모두에 대해서 우리는 지수-함수 시간의 알고리즘을 발견할 수 있지만, 그 중에 어느 것에서도 아무도 다항식-시간 알고리즘을 발견하지 못했다. 이와 같은 실패들은 아마도

P ≠ NP

라는 사실을 믿게 할지 모르지만 누군가가 P 에는 속하지 않지만 NP 에 속하는 NP 에 속하는 실제 언어를 생성하거나 또는 그와 같은 언어는 존재하지 않는다는 것을 증명할 때까지 이 문제는 미해결인 상태로 남아있다.