多項式時間還元可能性

第

章 多項式時間計算可能性の分析 第

章 多項式時間計算可能性の分析

6.1.

多項式時間還元可能性

定義

A

と

を任意の集合とする．

(1)

関数

多項式時間還元

は

から

への全域的関数

(b)

(c) h

は多項式時間計算可能．

(2) A

から

への多項式時間還元が存在するとき，

A

は

へ多項式時間還元可能という

このとき，次のように書く：

] )

( [

* x A h x B

x∈Σ ∈ ↔ ∈

P

A ≤m B

1/14

Chapter 6. Analysis on Polynomial-Time Computability

Chapter 6. Analysis on Polynomial-Time Computability

6.1. Polynomial-time Reducibility

Def.6.1:

Let A and B be arbitrary sets.

(1) function h: AÆB: polynomial-time reduction (a) h is a total function from Σ^∗ onto Σ^∗

(b)

(c) h is polynomial-time computable

．

(2) When there is a polynomial-time reduction from A to B

，

Then

，

] )

( [

* x A h x B

x ∈Σ ∈ ↔ ∈

P

A ≤m B

1/14

6.2.

多項式時間還元可能性に基づく完全性

6.2.1.

完全性の定義とその基本的性質

定義

計算量クラス

に対し，集合

が次の条件を満たすとき，

それを（ の下で）

完全という．

(a) L C [L A]

(b) A C

補注：条件

を満たす集合は

困難．

P

≤m

∀ ^∈ ≤^P_m

∈

7/14

例

クラス

の完全集合の例

3SAT, SAT, ExSAT, DHAM, KNAP, BIN, VC

など クラス

の完全集合

EVAL-IN-E, HALT-IN-E

など

6.2.Completeness based on Polynomial-time Reducibility

6.2.1. Definition of Completeness and its Basic Properties

Def.6.2: For a class C

，

(a) L C [L A]

(b) A C

Note

：

．

P

≤m

∀ ^∈ ≤_m^P

∈

7/14

Ex.6.5. Examples of NP-complete sets

3SAT, SAT, ExSAT, DHAM, KNAP, BIN, VC, etc EXP-complete sets

EVAL-IN-E, HALT-IN-E, etc.

定理

任意の

困難集合（含：

完全集合）

に対し，

(1) A P Æ C

⊆

対偶は

(2) A NP Æ C

⊆

対偶は

(3) A co-NP Æ C

⊆

対偶は

(4) A EXP Æ C

⊆

対偶は

∈

∈

∈

∈

∉

∉ ∉

∉

⊄⊄

⊄⊄

証明：

(1) B

を任意の

集合とすると，

は

困難だから，

A

B ≤_m^P

一方，

の仮定より，

（定理

）

も同様

∈ ∈

9/14

Theorem 6.3. For any C-hard (or C-complete) set A

，

(1) A P Æ C

⊆

(2) A NP Æ C

⊆

(3) A co-NP Æ C

⊆

⊆

∈

∈

∈∈

∉ ∉

∉∉

⊄⊄

⊄⊄

Proof

：

(1) Let B be any C-set. Then, since A is C-hard,

A

B ≤^P_m and by the assumption A P we have B P

（

）

∈ ∈

9/14

例

定理

の意味（クラス

を

完全集合とする．

定理

の対偶より，

NP P Î A P

定理

の対偶と定理

の対偶より，

A co-NP

つまり，

完全集合は

である限り，

多項式時間では認識できない．

∉

≠ ∉

≠

10/14

定理

(1) NP

⊆

定理

任意の

困難集合（含：

完全集合）

に対し，

(1) A P Æ C

⊆

対偶は

(2) A NP Æ C

⊆

対偶は

(3) A co-NP Æ C

⊆

対偶は

(4) A EXP Æ C

⊆

対偶は

∈

∈

∈

∈

∉

∉ ∉

∉

⊄⊄

⊄⊄

Ex.6.6: Meaning of Theorem 6.3

（

．

By the contraposition of Theorem 6.3(1) we have NP P Î A P

By the contraposition of Theorem 6.3(3) and that of Theorem 5.9(1)

，

A co-NP

That is

，

∉

≠ ∉

10/14

Theorem 5.9.

(1) NP

⊆

，

(1) A P Æ C

⊆

(2) A NP Æ C

⊆

(3) A co-NP Æ C

⊆

⊆

∈

∈

∈∈

∉ ∉

∉∉

⊄⊄

⊄⊄

NP-

完全集合は

である限り，

には入らない

集合である．

≠ _∩

NP

P

co-NP

NP

完全

co-NP

完全

11/14

NP-compete sets are NP-sets that do not belong to NP ^∩ co-NP unless P = NP.

NP

P

co-NP

NP-complete

co-NP -complete

11/14

例

定理

の意味（クラス

を

完全集合とする．

定理

の対偶（

ここでは

⊆

定理

の対偶（

ここでは

NP EXP Æ EXP NP ( NP

⊆

定理

の対偶（

ここでは

co-NP EXP ÆEXP co-NP ÆD co-NP

ところが定理

から であるから，

EXP-

完全集合は多項式時間では計算不可能．

⊄ ⊄

⊄

⊄ ⊄

⊄

∉ ∉

∉ ∉

∉ ∉

∉ ∉

∉

≠

≠

≠

⊄ ⊄

⊄ ^∴ ∉

∴

12/14

P yEXP

Ex. 6.7. Meaning of Theorem 6.3

（

．

Contraposition of Theorem 6.3(1)

（

⊆

Contraposition of Theorem 6.3(2)

（

NP EXP Æ EXP NP ( NP

⊆

Contraposition of Theorem 6.3(3)

（

co-NP EXP ÆEXP co-NP ÆD co-NP

But

，

，

，

EXP-complete sets are not computable in polynomial time

．

⊄ ⊄

⊄

⊄ ⊄

⊄

∉ ∉

∉ ∉

∉ ∉

∉ ∉

∉

≠

≠

≠

⊄

⊄

⊄ ∉

∴

∴

12/14

P yEXP

定理

任意の

完全集合 すべての集合

に対し，

(1) A B ÆB

は

困難．

(2) A B B C Æ B

は

完全．

P

≤m P

≤m ^{∧ ∈}

証明：

定義

より，

定理

より，

したがって，

すなわち，

は

困難．

[ ]

[ ]

P m

P P P

m m m

P m

L L A

L A A B L B

L L B

∀ ∈ ≤

≤ ∧ ≤ → ≤

∀ ∈ ≤ C

C

13/14

Theorem 6.4. A: any C-complete set For any set B we have

(1) A B ÆB is C-hard.

(2) A B B C Æ B is C-complete

．

P

≤m P

≤m ^{∧ ∈}

Proof

：

By Def. 6.2

By Theorem 6.2

，

，

That is

，

．

13/14

[ ]

[ ]

P m

P P P

m m m

P m

L L A

L A A B L B

L L B

∀ ∈ ≤

≤ ∧ ≤ → ≤

∀ ∈ ≤ C

C

EXPC {L: L

は

完全

は

完全

とすると，次の定理が成り立つ．

≡≡

定理

(1) EXPC P = φ

(2) EXP – (EXPC^∩ ∪P) φ≠

EXP

EXPC

P

定理

を仮定すると

(1) NPC P = φ

(2) NP – (NPC P) φ

∩

∪ ≠

≠

NP

NPC

P

NP_∩co-NP

}

14/14

EXPC {L: L is EXP-complete}

NPC {L: L is NP-complete}

Then, we have the following theorems

．

≡≡

Theorem 6.5.

(1) EXPC P = φ

(2) EXP – (EXPC^∩ ∪P) φ≠

EXP

EXPC

P Theorem 6.6: Assuming P NP

(1) NPC P = φ

(2) NP – (NPC P) φ

∩ ∪ ≠

≠

NP

NPC

P

NP_∩co-NP

}

14/14

6.2.2.

完全性の証明

(NP)

完全性の証明方法

(I)

定義通りに

すべての

について示す

(II)

すでに完全であることがわかっている問題を利用する

(I)

の例

定理

定理

≒

の定理

で

を模倣

(II)

の例

例

定理

は一般のグラフ上でNP完全

DHAM

は平面グラフに限定しても

完全

DHAM

は「頂点の次数＝

」に限定しても

完全

は

部グラフに限定しても

完全

1/11

P

≤m

基本的には

1. 多項式時間で動く標準プログラムを考えて 2. プログラムの動作を命題論理式で模倣する

→とても大変

手間がかかる

などは、形式

が一様なので扱い

やすい

6.2.2. Proof for completeness

Two ways to prove (NP-)completeness

(I) show ‘for all L’ according to definition (II) use some known complete problems Ex for (I) : Theorem 6.7,

Theorem 6.9(

≒

Ex for (II): Example 6.4(3SAT DHAM), Theorem 6.10, … DHAM is NP-complete for general graphs

DHAM is NP-complete even for planar graphs

DHAM is NP-complete even for graphs with max degree=3 DHAM is NP-complete even for bipartite graphs …

1/11

P

≤m

Basically…

1. For any program in standard form, 2. simulate it by SAT formulae

→

since, e.g., 3SAT has a uniform structure.

定理

以下にあげる集合はすべて

完全

からの還元）

(2) DHAM, VC (3SAT

からの還元）

(3) KNAP, BIN (3SAT

からの還元と

2/11

(II) NP

完全性がわかっている問題からの多項式時間還元

2. DHAM ≤_m^P

頂点の次数が高々

に制限された

P

≤m

Vertex Cover:

すべての辺の、少なくとも一方の頂点を含む集合

Hamiltonian cycle:

すべての頂点を一度ずつ通る閉路

おまけ

は次数高々

でも

完全。

高々

だと多項式時間で計算可能。

Theorem 6.10 The following sets are all NP-complete:

(1) 3SAT, SAT (reduction from ExSAT

）

）

(3) KNAP, BIN (reduction from 3SAT and KNAP BIN)≤_m^P

(II) Polynomial time reductions from NP-complete problems:

1. 3SAT VC

2. DHAM DHAM with vertices of degree ≤_m^P

≦

P

≤m

2/11

Vertex Cover: a vertex set that contains

at least one endpoint for each edge

Hamiltonian cycle: a cycle that visits each vertex exactly once

Note : DHAM remains NP-complete even if max degree 3.

But it is polynomial time solvable if max degree 2.

定理

は

完全問題

P

≤m

3/11

[

証明

∈

なので、

であることを示せばよい。

論理式

が与えられたとする。

F

から以下の条件を満たすグラフと自然数の組

が 多項式時間で構成できることを示す：

F

を

にする割当が存在する⇔

がサイズ

の頂点被覆を持つ

の構成

は

変数

項とする

1. F

の各変数

に対し、頂点

と、辺

を加える

2. F

の各項

∨

∨

に対し、頂点

と辺

を加える

3.

項

のリテラル

が

のときは辺

を、￢

のときは辺

を加える。

4. k = n+2m

Theorem 6.10(2) : VC is NP-complete

3/11

[Proof] Since VC

∈

For given formula F(x₁,x₂,…,x_n), we construct a pair <G,k>

of a graph and an integer in polynomial time.

There is an assignment that makes F()=1

⇔

Construction of G (F has n variables and m clauses):

1. add vertices x_i⁺,x_i^- and the edge (x_i⁺,x_i^-) for each variable x_i in F 2. For each clause C_j=(l_i1

∨

∨

three edges (l_i1,l_i2), (l_i2,l_i3), (l_i3,l_i1)

3. add the edge (l_i1,x_i⁺) if the literal l_i1 is x_i, or add (l_i1,x_i^-) if it is

￢

4. let k = n+2m

P

≤m

F

を

にする割当が存在する⇔

がサイズ

の頂点被覆を持つ

の構成

は

変数

項とする

1. F

の各変数

に対し、頂点

と、辺

を加える

2. F

の各項

∨

∨

に対し、頂点

と辺

を加える

3.

項

のリテラル

が

のときは辺

を、￢

のときは 辺

を加える。

4. k = n+2m

例

∨

∨

∧

￢

∨

∨

∧

∨￢

∨

x₁

x₂ x₃

￢

x₁

￢

G k = 4+2

×

4/11

Ex: F(x₁,x₂,x₃,x₄) = (x₁

∨

∨

∧

￢

∨

∨

∧

∨￢

∨

x₁

x₂ x₃

￢

x₁

￢

G k = 4+2

×

4/11 There is an assignment that makes F()=1

⇔

Construction of G (F has n variables and m clauses):

1. add vertices x_i⁺,x_i^- and the edge (x_i⁺,x_i^-) for each variable x_i in F 2. For each clause C_j=(l_i1

∨

∨

three edges (l_i1,l_i2), (l_i2,l_i3), (l_i3,l_i1)

3. add the edge (l_i1,x_i⁺) if the literal l_i1 is x_i, or add (l_i1,x_i^-) if it is

￢

4. let k = n+2m

F

を

にする割当が存在する⇔

がサイズ

の頂点被覆を持つ

の構成は、与えられた

から

のサイズに対する多項式時間

で可能 。したがって以下を示せばよい

例

∨

∨

∧

￢

∨

∨

∧

∨￢

∨

x₁

x₂ x₃

￢

x₁

￢

G k = 4+2

×

G

の構成から任意の頂点被覆

は

のどちらかを含む

C_j

の

頂点中、最低

つ含む よって

≧

である。

観察

5/11

It is easy to see that the construction of G from F can be done in polynomial time of the size of F. Hence, we show that…

Ex: F(x₁,x₂,x₃,x₄) = (x₁

∨

∨

∧

￢

∨

∨

∧

∨￢

∨

x₁

x₂ x₃

￢

x₁

￢

G k = 4+2

×

From the construction of G,

any vertex cover S should contain

at least one of x_i⁺ or x_i^-

at least 2 of 3 vertices in C_j Hence we have |S|

≧

Observation:

5/11

There is an assignment that makes F()=1

⇔

￢

F

を

にする割当が存在する⇒

がサイズ

の頂点被覆を持つ

例

∨

∨

∧

￢

∨

∨

∧

∨￢

∨

x₁

x₂ x₃

￢

x₁

￢

G k = 4+2

×

1.

それぞれの変数

が

なら

を

に入れる

なら

を

に入れる

2.

それぞれの項

は充足されているので、

最低

つのリテラル

については変数との間の辺

は

によって被覆されている。したがって、それ以外の 二つのリテラル

を

に入れる。

観察 より、S はサイズ

の頂点被覆になる。

⇒

6/11

Ex: F(x₁,x₂,x₃,x₄) = (x₁

∨

∨

∧

￢

∨

∨

∧

∨￢

∨

x₁

x₂ x₃

￢

x₁

￢

G k = 4+2

×

1. Put x_i⁺ if x_i=1

into S for each x_i.

2. Since each clause C_j=(l_i1,l_i2,l_i3) is satisfied, at least one literal, say l_i1, the edge (l_i1,x_i1) is covered by the variable x_i1. Therefore, put the remaining literals (l_i2,l_i3) into S.

Observation, S is a vertex cover of size k.

⇒

If there is an assignment that makes F()=1, 6/11 G has a vertex cover of size k

x_i^- if x_i=0

From the

G

がサイズ

の頂点被覆を持つ⇒

を

にする割当が存在する

例

∨

∨

∧

￢

∨

∨

∧

∨￢

∨

x₁

x₂ x₃

￢

x₁

￢

G k = 4+2

×

1.

2.

さらに各変数

については

か

の一方しか、

各項

についてはちょうど

つの頂点しか

に含むことができない。

観察 より、被覆S は項から

個、変数から

個の頂点を含む。

⇒

が

に含まれるなら

x_i^-

が

に含まれるなら

という割当は

を充足する。

3.

よって各項

は

に含まれないリテラル

を含むが、

これに付随する辺は他方が被覆されていなければならない。

QED.

7/11

Ex: F(x₁,x₂,x₃,x₄) = (x₁

∨

∨

∧

￢

∨

∨

∧

∨￢

∨

x₁

x₂ x₃

￢

x₁

￢

G k = 4+2

×

1. From Observation,

⇒

x_i=0 if x_i^- in S The following assignment satisfies F:

QED.

7/11 If G has a vertex cover of size k, there is an assignment s.t. F()=1

a cover S contains 2m vertices from the clauses, and n vertices from the variables.

3. Hence each clause C_j contains exactly one literal l_i which is not in S, and hence incident edge should be covered by a variable vertex.

2. Thus the cover S contains exactly one of x_i⁺ and x_i^- and exactly two literals of a clause C_j.

￢

充足できない例

F(x₁,x₂,x₃) = (x₁

∨

∨

∧

￢

∨￢

∨￢

∧

∨

∨

∧

￢

∨

∨￢

x₁⁺ x₁^- x₂⁺ x₂^- x₃⁺ x₃^-

x₁

x₁ x₁

￢

￢

￢

x₂

x₃ x₃ G

k = 3+2

×

￢

x₂

￢

充足できない

では、どのリテラルも頂点でカバーされていない 項が必ず存在する。この項のリテラルは

つとも

に

入れざるを得ない。よって

のサイズは

以上になる。

Unsatisfiable example:

F(x₁,x₂,x₃) = (x₁

∨

∨

∧

￢

∨￢

∨￢

∧

∨

∨

∧

￢

∨

∨￢

x₁⁺ x₁^- x₂⁺ x₂^- x₃⁺ x₃^-

x₁

x₁ x₁

￢

￢

￢

x₂

x₃ x₃ G

k = 3+2

×

￢

x₂

￢

When F is unsatisfiable, it contains at least one clause such that each literal is not covered by a vertex. So, Vertex Cover should

contain three literals in the clause. Hence any vertex cover has size at least k+1.

定理

次数高々

の有向グラフ上の

は

完全問題

P

≤m

[

証明

上記の問題を

と略記する

DHAM_≦5

が

に属するのは、

が

に

属することから自明。したがって完全性を示せばよい。

DHAM DHAM_≦5

を示す。

次数

頂点に付 随する辺の本数

v

v

アイデア

次数

の頂点

左

の

入ってくる辺集合

と

出ていく辺集合

を右図 の

で置き換える 左図で

を

度だけ通る 閉路と右図で

を

度だ け通る閉路は対応する。

v

v

9/11

Theorem: DHAM on a directed graph with max. degree=5 (abb. DHAM_≦5) is NP-complete

P

≤m

[Proof]

Since DHAM

∈

∈

.

degree: the number of edges incident to a vertex

v

v Idea:

Replace the set of “arcs to v”

and the set of “arcs from v”

by a right ‘gadget’.

A Hamiltonian cycle through v on the original graph

corresponds to the

Hamiltonian cycle through v on the resultant graph.

v

v

9/11