34. NP-Completeness

지금까지 본 알고리즘의 대부분은 다항 시간 알고리즘이었다. 허나 모든 문제가 다항 시간 알고리즘인 것은 아니다. 여기서는 다항 시간인지 아닌지 알려지지 않은 NP-난해 알고리즘을 다룬다. 방향그래프에서 단일 지점으로부터의 최단 경로는 O(VE) 시간에 찾을 수 있다. 최장 단순 경로는 NP-완전이다. 연결방향그래프에서 각 간선을 한 번씩 방문하는 경로인 오일러 순회는 O(E) 시간에 찾을 수 있다. 방향그래프에서 각 정점을 한 번씩 방문하는 경로인 해밀토니언 회로가 있는지 판정하는 것은 NP-완전이다. 논리식은 어떤 논리값들을 대입했을 때 1이 되면 만족 가능하다고 한다. k개의 변수를 AND, OR, 부정만 써서 만드는 k-논리곱 정규형에 대해 2-CNF의 만족 가능성을 찾는 것은 다항 시간에 가능하지만 3-CNF는 NP-완전이다.

NP-completeness and the classes P and NP

P, NP, NPC에 대해 알아보자. P는 다항 시간에 풀 수 있는 문제들이다. NP는 다항 시간에 검증 가능한 문제들이다. 당연하지만 P ⊆ NP이다. NPC, 즉 NP-완전은 최소한 어떤 NP 문제만큼은 어려운 NP 문제들이다. NP-완전 문제 중 하나라도 다항 시간에 풀 수 있으면 모든 NP 문제는 다항 시간에 풀 수 있다. 어떤 문제가 NP-완전 문제라면 근사 알고리즘을 구하는 것이 낫다.

Overview of showing problems to be NP-complete

어떤 문제가 NP-완전인지 보일 때는 그 문제가 최소한 얼마나 어려운지를 보인다. 세 개의 핵심적인 개념이 있다:

  • 결정 문제 vs 최적화 문제. 많은 문제는 가능해가 연관된 값이 있을 때 그 중 가장 최고의 값과 연관된 가능해를 찾는 최적화 문제이다. 이와 달리 결정 문제는 문제가 1 아니면 0인 문제이다. NP-완전 문제는 결정 문제들이지만, 결정 문제와 최적화 문제에는 연관이 있다: 최적화 문제가 쉽다면 그와 관련된 결정 문제는 최소한 그만큼은 쉽다. 결정 문제가 어렵다면 그와 관련된 최적화 문제는 최소한 그만큼은 어렵다.
  • 환원 문제. 두 문제가 모두 결정 문제일 때도 둘 간의 난이도를 비교할 수 있다. 특정 문제의 입력을 그 문제의 인스턴스라 하자. 결정 문제 B를 다항 시간에 풀 수 있고 결정 문제 A의 인스턴스 α를 결정 문제 B의 인스턴스 β로 변환할 때 그 변환이 다항 시간이 걸리고 두 답이 같을 때 이를 다항 시간 환원 알고리즘이라 하고 이러면 결정 문제 A를 다항 시간에 풀 수 있다. 다항 시간 환원 알고리즘을 반대로 써서 어떤 문제가 NP-완전인지를 보일 수 있다. A가 NP-완전이면 B도 NP-완전이다.
  • 첫 NP-완전 문제. 논리 조합 회로는 첫 NP-완전 문제이다.

Chapter outline

이 장은 NP-완전성에 대해 다룬다.

34.1. Polynomial time

먼저 다항 시간 알고리즘은 계산 가능하다고 하자. 처음에 \Theta(n^{100}) 알고리즘이 나오면 실용적인 관점에서는 계산 불능이지만 대개 이를 더 최적화한 알고리즘이 나온다. 또한, 많은 계산 모델에서 하나의 계산 모델에서 다항 시간에 풀 수 있는 문제는 다른 모델에서도 다항 시간에 풀 수 있다. 그리고 다항 시간 알고리즘의 합성은 다항 시간이다.

Abstract problems

추상 문제 Q는 문제 인스턴스 집합 I와 문제 집합 S간 이진 관계이다. 추상 문제에는 크게 결정 문제최적화 문제 등이 있다.

Encodings

추상 오브젝트의 집합 S의 암호화는 S로부터 이진 문자열로의 매핑 e이다. 컴퓨터 알고리즘은 이 집합의 암호화를 입력으로 받는 실체 문제푼다. 이 때 길이 n의 문제 인스턴스를 받았을 때 해를 O(T(n))에 낼 수 있으면 O(T(n))에 푼다 한다. T(n)이 다항식이면 다항 시간 해결 가능이라 한다. 복잡도 클래스 P는 다항 시간 해결 가능한 실체 문제들이다. 문제를 어떻게 인코딩하냐에 따라 (예를 들어 단항이냐 아니냐에 따라) 복잡도 클래스의 분류도 달라질 수 있기 때문에 추상 문제에 대해서는 복잡도 클래스를 나누는 것이 불가능하다. 함수 f : \{0, 1\}^{\ast} \to \{0, 1\}^{\ast}는 임의의 입력에 대해 답을 다항 시간에 내는 알고리즘이 있다면 다항 시간 계산 가능이라 한다. 문제 인스턴스 집합 I에 대해 두 암호화간 다항 시간 변환이 존재하면 다항 시간 관련되었다 한다.

Lemma. Q가 인스턴스 집합 I에 대한 추상 결정 문제이고 e_{1}, e_{2}가 다항 시간 관련된 I의 암호화라 하면 e_{1}(Q) \in P \Leftrightarrow e_{2}(Q) \in P이다.

그러므로 다항 시간 관련된 인코딩들간에는 추상 문제의 복잡도 차이가 없다. 여기서 추상 문제를 인코딩할 때는 이진 문자열로 표준 인코딩하는 것으로 하자.

A formal-language framework

알파벳 Σ는 기호의 유한 집합이다. Σ 위의 언어 L은 Σ의 기호로 만들어진 문자열의 집합이다. 빈 문자열은 ε, 빈 언어\emptyset으로 한다. 언어에 대해 합집합, 교집합, 여집합, 접합, 클로저/클리네 스타도 적용할 수 있다. 결정 문제의 알고리즘에 대해 어떤 해의 답이 1이면 그 알고리즘은 그 해를 수용하고 0이면 기각한다고 한다. A에 의해 수용되는 언어는 수용되는 해의 집합이다. L이 A에 의해 수용되더라도 L에 속하지 않은 원소가 A에 의해 기각된다는 보장은 없다. 무한 루프가 돌 수도 있다. 이런 경우가 없다면 언어 L이 A에 의해 결정된다고 한다. L이 A에 의해 수용될 때 다항 시간 안에 되면 다항 시간에 수용된다 한다. L이 A에 의해 결정될 때 다항 시간 안에 되면 다항 시간에 결정된다 한다. 복잡도 클래스는 수행 시간같은 복잡도 측정에 의해 판정되는 언어의 집합이다.

Theorem. P는 다항 시간에 수용되는 언어의 집합이다.

L \in P라고 해서 L을 수용하는 알고리즘의 시간 상한은 알 수 없다.

34.2. Polynomial-time verification

이제 다항 시간에 검증할 수 있는 언어들을 알아보자.

Hamiltonian cycles

비방향그래프의 해밀토니언 회로는 각 정점을 순회하는 단순 경로이다. 해밀토니언 회로가 있는 그래프는 해밀토니언, 아니면 비해밀토니언이라 한다. 그래프의 해밀토니언 여부를 판정하는 문제를 해밀토니언 회로 문제라 한다. 이에 대한 나이브한 알고리즘은 다항 시간이 아니다.

Verification algorithms

해밀토니언 회로 해의 정당성을 검증하는 건 O(n^{2})이므로 해밀토니언 문제는 다항 시간 검증 가능하다. 검증 알고리즘은 입력 문자열과 그에 대한 인증 문자열을 받는 이인자 알고리즘이다. 입력 문자열 x에 대해 A(x, y) = 1이 되는 인증 문자열이 있으면 A가 x를 검증한다. A에 의해 검증되는 문자열의 집합은 A에 의해 검증되는 언어라 한다.

The complexity class NP

복잡도 클래스 NP다항 시간검증 가능한 알고리즘의 집합이다. HAM-CYCLE은 NP이다. P ⊆ NP이다. P = NP인지는 알려지지 않았으나 많은 사람들은 P ≠ NP라 믿는다. 여집합이 NP인 알고리즘을 복잡도 클래스 co-NP라 하는데, P ⊆ NP ∩ co-NP이다. P = NP ∩ co-NP인지는 알려지지 않았다.

34.3. NP-completeness and reducibility

NP-완전 문제 중 하나라도 다항 시간에 풀 수 있으면 모든 NP 문제는 다항 시간에 풀 수 있다. 그러나 NP-완전 문제 중 단 하나도 다항 시간 해결 알고리즘은 알려지지 않았다. HAM-CYCLE은 NP-완전 문제이다. NP-완전 문제는 NP에서 가장 어려운 문제들이다.

Reducibility

언어 L_{1}은 다른 언어 L_{2}환원 알고리즘으로 계산되는 환원 함수를 통해 다항 시간에 인스턴스를 변환할 수 있고 그 변환한 인스턴스를 받는 문제와 해집합이 같으면 다항 시간 환원 가능하다 한다.

Lemma. L_{1}L_{2}로 다항 시간 환원 가능하면 L_{2} \in P \Rightarrow L_{1} \in P이다.

NP-completeness

L ∈ NP이고 모든 L’ ∈ NP에 대해 L’에서 L로 다항 시간 환원 가능하면 L은 NP-완전이라 한다. 모든 L’ ∈ NP에 대해 L’에서 L로 다항 시간 환원 가능하지만 L ∈ NP인지는 모르면 L은 NP-난해라 한다.

Theorem. NP-완전 문제 중 하나라도 다항 시간 해결 가능하다면 P = NP이다. NP 문제 중 하나라도 다항 시간 해결이 불가능하다면 NP-완전 문제 중 다항 시간 해결 가능한 문제는 없다.

그러므로 P ≠ NP 문제는 NP-완전 문제에 대한 연구로 환원된다. 많은 사람들은 P ≠ NP라 믿는다.

Circuit satisfiability

회로 만족가능성 문제가 진짜로 NP-완전인지를 알아보자. 논리 조합 원소는 논리 입력과 출력을 상수 개 갖고 잘 정의된 함수를 수행하는 회로 원소를 말한다. 이들은 논리 게이트라 불리는 단순 논리 함수를 계산한다. NOT 게이트(반전기), AND 게이트, OR 게이트가 있다. NOT 게이트는 단일 이진 입력을 받고 그 반대값의 이진 출력을 낸다. 이 게이트들의 출력값은 진리표로 나타낼 수 있다. AND나 OR 게이트는 3개 이상의 입력으로 일반화될 수 있다. 논리 조합 회로와이어로 연결된 논리 조합 원소들이다. 와이어에 들어가는 입력의 수는 팬아웃이라 한다. 와이어에 출력이 없다면 원환 입력이라 한다. 와이어에 입력이 없다면 원환 출력이라 한다. 논리 조합 회로에는 순환이 없다. 논리 조합 회로의 진리값 대입은 논리 입력값의 집합이다. 출력값을 1로 만드는 진리값 대입을 만족 대입이라 하며 이가 존재하면 이 회로는 만족 가능하다 한다. 회로 만족가능성 문제는 논리 조합 회로가 만족가능한지를 찾는 문제이다.

Lemma. 회로 만족가능성 문제는 NP이다.

CIRCUIT-SAT가 NP-난해인지 보이려면 컴퓨터 하드웨어에 대해 이해할 필요가 있다. 프로그램 카운터로 불리는 특별한 메모리 위치는 어떤 명령문을 다음에 실행해야 할지를 나타낸다. 실행의 어떤 시점에서도, 컴퓨터의 메모리는 전체 계산 상태를 갖고 있다. 컴퓨터 메모리의 특정 상태를 배치라 하자.

Theorem. 회로 만족가능성 문제는 NP-난해이다.

Theorem. 회로 만족가능성 문제는 NP-완전이다.

34.4 NP-completeness proofs

어떤 언어가 NP-완전인지를 보이는 것은 다음이 기본이다.

Lemma. 어떤 NP-완전 L’에 대해 L이 L’로부터 다항 시간 환원 가능하면 L은 NP-난해이다. L ∈ NP이면 L ∈ NPC이다.

Formula satisfiability

식 만족가능성 문제는 SAT 문제로 나타낼 수 있다. SAT의 인스턴스는 n개의 논리 변수, m개의 논리 연결식, 괄호들로 구성된 논리식이다. 논리식의 진리값 대입은 그 변수의 집합이다. 출력값을 1로 만드는 진리값 대입을 만족 대입이라 하며 이가 존재하면 이 회로는 만족 가능하다 한다.

Theorem. 논리식의 만족가능성 문제는 NP-완전이다.

이는 논리식을 로 분해해 분석해서 증명할 수 있다.

3-CNF satisfiability

3-CNF 만족가능성은 다음과 같이 정의할 수 있다. 논리식의 리터럴은 변수나 그 부정의 등장이다. 논리식 중 하나 이상의 절을 OR한 들을 AND한 것들을 논리곱 정규형(CNF)이라 한다. 최대 3개의 서로 다른 리터럴을 가진 논리곱 정규형을 3-논리곱 정규형(3-CNF)이라 한다.

Theorem. 3-논리곱 정규형 논리식의 만족가능성 문제는 NP-완전이다.

이를 증명하기 위해서는 논리합 표준형(DNF)을 구성한 뒤 드 모르간의 법칙을 사용한다.

34.5 NP-complete problems

여러 NP-완전 문제를 알아보자.

34.5.1 The clique problem

비방향그래프의 클리크는 완전부분그래프이며 그 정점 개수를 크기라 한다. 클리크 문제는 최대 클리크 크기를 구하는 최적화 문제 또는 크기 k의 클리크를 구하는 결정 문제로 볼 수 있다.

Theorem. 클리크 문제는 NP-완전이다.

이는 논리식 절로 변경해 리터럴이 일관성 있는지를 분석해 임의의 3-CNF-SAT 인스턴스로부터 CLIQUE의 특정한 인스턴스를 환원해 증명할 수 있다. 단 이것은 특정한 3-CNF-SAT 인스턴스로부터 CLIQUE의 임의의 인스턴스를 환원하는 것이 아니다.

34.5.2 The vertex-cover problem

비방향그래프의 정점 덮개는 (u, v) ∈ E이면 u ∈ V’ 또는 v ∈ V’가 되는 V’ ⊆ V이다. 정점 덮개의 크기는 정점 수이다. 정점 덮개 문제는 주어진 그래프의 최소 크기 정점 덮개를 찾는 문제이다.

Theorem. 정점 덮개 문제는 NP-완전이다.

이는 그래프의 여집합을 통해 분석한다.

34.5.3 The hamiltonian-cycle problem

Theorem. 해밀토니언 회로 문제는 NP-완전이다.

이는 그래프의 위젯선택 정점 등을 통해 분석한다.

34.5.4 The traveling-salesman problem

여행 외판원 문제는 외판원이 도시들을 한 번씩만 순회할 때 간선으로부터 발생하는 비용의 합을 최소화시키는 문제이다.

Theorem. 여행 외판원 문제는 NP-완전이다.

34.5.5 The subset-sum problem

부분집합-합 문제는 양의 정수의 유한집합 S의 대상 정수 t > 0이 주어졌을 때 합이 t가 되는 S의 부분집합 S’ ⊆ S를 찾는 문제이다.

Theorem. 부분집합-합 문제는 NP-완전이다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중