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

計算量クラス間の定義を概観すると…

クラスNPの定義(定義5.2) 集合LがクラスNPに入る ⇔

以下を満たす多項式qと多項式時間計算可能述語Rが存在:

各x∈Σ^*でx∈L⇔∃w∈ Σ^*：|w|≦q(|x|)[R(x,w)]

クラスco-NPの定義(定理5.5) 集合Lがクラスco-NPに入る ⇔

以下を満たす多項式qと多項式時間計算可能述語Rが存在:

各x∈Σ^*でx∈L⇔∀w∈ Σ^*：|w|≦q(|x|)[R(x,w)]

クラスPの定義(5章) 集合LがクラスPに入る ⇔

以下を満たす多項式時間計算可能述語Rが存在:

各x∈Σ^*でx∈L⇔R(x)

0/14

Observation of the definitions of the classes…

Def: Class NP(Def 5.2) Set Lis in the class NP ⇔

There exists a poly qand a poly-time computable pred. Rs.t.

for each x∈Σ^*, x∈L⇔∃w∈ Σ^*：|w|≦q(|x|)[R(x,w)]

Def: Class co-NP(Theorem 5.5) Set Lis in the class co-NP ⇔

There exists a poly qand a poly-time computable pred. Rs.t.

for each x∈Σ^*, x∈L⇔∀w∈ Σ^*：|w|≦q(|x|)[R(x,w)]

Def: Class P(Chapter 5) Set Lis in the class P ⇔

There exists a poly-time computable predicate Rsuch that for each x∈Σ^*, x∈L⇔R(x)

0/14

定理5.9.

(1) NP⊆co-NPÆNP= co-NP (2) co-NP⊆NPÆNP= co-NP (3) NP≠co-NP ÆP≠NP.

補注: (3)より，NP ≠co-NPの証明は，P NPの証明より難しい．≠ 証明： (1) NP⊆co-NPÆNP= co-NP ((2)の証明も同様）

任意のL co-NPに対してL NPが示せれば，co-NP⊆NP

が証明できるので，仮定のNP⊆co-NPと合わせてNP= co-NP が言える．

L co-NP L NP (定義5.3より）

L co-NP (NP⊆co-NPより）

L NP (定義5.3とL=Lより）

∈ ∈

∈ ∈

∈

∈ ＝

11/12

Theorem 5.9

(1) NP⊆co-NPÆNP= co-NP (2) co-NP⊆NPÆNP= co-NP (3) NP≠co-NP ÆP≠NP.

Note: from (3) the proof for NP co-NPis harder than that for P NP．

≠ ≠

Proof： (1) NP⊆co-NPÆNP= co-NP (proof of (2) is similar）

Since co-NP⊆NPis shown if we prove L NP for any L co-NP Combining it with the assumption NP⊆co-NP, we have NP= co-NPand so

L co-NP L NP (by Definition 5.3）

L co-NP (NP⊆co-NP）

L NP (Definition 5.3 and L=L）

∈ ∈

∈ ∈

∈

∈ ＝

11/12

(3) NP≠co-NP ÆP≠NP.

対偶：P=NPÆNP = co-NP P=NPと仮定すると，すべてのLに対し

L NP L P （P= NPより）

L P (演習問題5.5)

L NP (P= NPより）

L(= L) co-NP (定義5.3より)

NP = co-NP 証明終

∴

∈ ∈

∈∈

＝ ∈ ー

ー

↔

↔

↔

↔

NP≠co-NPが正しいと

12/12

(3) NP≠co-NP ÆP≠ NP.

Contraposition：P=NPÆNP = co-NP If we assume P=NP, for any Lwe have

L NP L P （P= NP）

L P (Exercise 5.5)

L NP (P= NP） L(= L) co-NP (Definition 5.3)

NP = co-NP Q.E.D.

∴

∈ ∈

∈∈

＝ ∈ ー

ー

↔

↔

↔

↔

If NP ≠co-NPis true,

12/12

第

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

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

6.1. 多項式時間還元可能性 定義6.1:

AとBを任意の集合とする．

(1) 関数h: AÆB: 多項式時間還元(polynomial-time reduction) (a) hはΣ^∗からΣ^∗への全域的関数

(b)

(c) hは多項式時間計算可能．

(2) AからBへの多項式時間還元が存在するとき，

AはBへ多項式時間還元可能という(polynomial time reducible).

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

] ) ( [

* x A hx B

x∈Σ ∈ ↔ ∈

P

A≤mB

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 Aand Bbe arbitrary sets.

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

(c) his polynomial-time computable．

(2) When there is a polynomial-time reduction from Ato B，

we sayAis polynomial-time reducible to B.

Then，we denote by

] ) ( [

* x A h x B

x∈Σ ∈ ↔ ∈

P

A≤mB

1/14

P

A≤mB 多項式時間の範囲内では，Aの難しさ≤Bの難しさ 定理6.1. A≤_m^PBのとき，

(1) B PÆA P.

(2) B NPÆA NP.

(3) B co-NP ÆA co-NP.

(4) B EXPÆA EXP.

∈

∈

∈

∈

∈

∈

∈

∈

補注：クラスEは例外．一般には，B∈EÆA∈Eとはならない．

例6.2:ONE {1}と定義するとき，クラスPのすべての集合Lに ついて

≡

PONE L≤m

が成り立つ． h(x) 1, x Lのとき，

0, その他のとき

≡

{

と定義すると，(1) hはΣ^∗からΣ^∗への全域的関数．

(2)

(3) hは多項式時間計算可能(L PÆx Lの判定も多項式時間内）

ONE]

) ( [

* ∈ ↔ ∈

Σ

∈ x L hx x

∈

∈

2/14 _P

A≤mB within polynomial time，hardness of A≤that of B 定理6.1 A≤^P_mB^{leads to，}

∈

∈

∈

∈

∈

∈

∈

Note：class Eis exceptional．Generally, B∈EÆA∈Eis not true．

Ex.6.2:If we define ONE {1}，for each set L≡ in Pwe have

PONE L≤m

h(x) 1, if x L，

0, otherwise

≡

{

(1) his a total function from Σ^∗onto Σ^∗． (2)

(3) hxis polynomial-time computable(so is computation L∈Σ*[x∈L↔h(x)∈ONE] PÆx L）

∈

∈ If we define

2/14

(1) B PÆA P.

(2) B NPÆA NP.

(3) B co-NP ÆA co-NP.

(4) B EXPÆA EXP.

∈

定理6.2:A, B, C: 任意の集合 (1)

(2)

P m

P P P

m m m

A A

A B B C A C

≤

≤ ∧ ≤ → ≤

3/14

P P P

m m m

P m

A ≡ B ↔ A ≤ B ∧B ≤ A

≡ 定義：

は同値関係

Theorem 6.2:A, B, C: arbitrary sets

3/14

Def is an equivalence relation.

P P P

m m m

P m

A ≡ B ↔ A ≤ B ∧B ≤ A

≡

： (1)

(2)

P m

P P P

m m m

A A

A B B C A C

≤

≤ ∧ ≤ → ≤

命題論理式の充足可能性問題の間の関係

2SAT （命題論理式充足性問題：二和積形式）

3SAT （命題論理式充足性問題：三和積形式）

SAT （命題論理式充足性問題）

ExSAT （拡張命題論理式充足性問題）

2SAT≤_m^P3SAT 同様に，

3SAT SAT ExSAT

2SAT 3SAT SAT ExSAT (6.1)

P P

m m

P P P

m m m

≤ ≤

≤ ≤ ≤

ここで

ExSAT ≤^P_m 3SAT であることを示せると，

3SAT ≡^Pm SAT ≡^Pm ExSAT となる．

4/14

•高々k個…自明

•ちょうどk個…

¾同じリテラルを使ってよいなら簡単。

¾だめなら…考えてみよう！

Relation among satisfiability problems of propositional expressions 2SAT （propositional satisfiability problem）

3SAT SAT

ExSAT （extended propositional satisfiability problem）

2SAT≤^P_m3SAT Similarly，

3SAT SAT ExSAT

2SAT 3SAT SAT ExSAT (6.1)

P P

m m

P P P

m m m

≤ ≤

≤ ≤ ≤

Here, if we can show ExSAT ≤_m^P 3SAT then we have

3SAT ≡^P_m SAT ≡_m^P ExSAT

4/14

•at most k…trivial

•exactly k…

¾easy if you can repeat the same literal.

¾the other case … good exercise!

例6.3: ExSATから3SATへの還元

3 3 2 2 1 3 2 1

1(x,x,x) [[x x ] [x x]] x

E ≡ ↔ → ∧ ∨¬

]]

[ [ ]]

[ [ ) , ,

( _{1 2 3 1 1 2 3 2 3 4}

1 x x x U U U x U U U

F ≡ ∧ ↔ ∨¬ ∧ ↔ →

]]

[ [ ]]

[

[U₃↔ x₁↔x₂ ∧U₄↔ x₂∧x₃

∧

このとき，[E₁が充足可能] [F₁が充足可能] (6.2) F₁は三和積形式に直しやすい形になっている．

F₁の構成方法

↔

∨

→

∧

¬

↔

x₁ x₂ x₃ (1) (2) (3) (4)

1 2 3

2 3 4

3 1 2

4 2 3

(1)

(2) [ ]

(3) [ ]

(4)

V V x

V V V

V x x

V x x

≡ ∨ ¬

≡ →

≡ ↔

≡ ∧

F₁を構成するために，V_i→U_iとし，V_iの定義式を で結ぶ∧

5/14 Ex. 6.3: Reduction from ExSAT to 3SAT

3 3 2 2 1 3 2 1

1(x,x,x) [[x x] [x x]] x

E ≡ ↔ → ∧ ∨¬

]]

[ [ ]]

[ [ ) , ,

( _{1 2 3 1 1 2 3 2 3 4}

1 x x x U U U x U U U

F ≡ ∧ ↔ ∨¬ ∧ ↔ →

]]

[ [ ]]

[

[U₃↔ x₁↔x₂ ∧U₄↔ x₂∧x₃

∧

Then, [E₁is satisfiable] [F₁is satisfiable] (6.2) F₁is easier to be converted to 3SAT form．

How to construct F₁

↔

∨

→

∧

¬

↔

x₁ x₂ x₃ (1) (2) (3) (4)

1 2 3

2 3 4

3 1 2

4 2 3

(1)

(2) [ ]

(3) [ ]

(4)

V V x

V V V

V x x

V x x

≡ ∨ ¬

≡ →

≡ ↔

≡ ∧

To constructF₁ we let V_i→U_i，and connect expressions of V_iby ∧ 5/14

F₁の構成方法より，

(1)各U_iの値をV_i(x₁, x₂, x₃)としない限り，F₁は真にはならない．

(2)各U_iの値をV_i(x₁, x₂, x₃)としたとき，F₁＝E₁

上の性質が成り立つことは，帰納法を用いるなどして証明可能．

証明は省略．

三和積形式への変換 a b= a b

a b= (a b) (b a) = [ a b] [ b a]であることを用いる．

→ ¬

¬ ¬

↔ → ∧ → ∧

∨ ∨ ∨

1 2 3 1 2 3 1 2 2

1 2 3 1 2 2

[ ] [ ] [ [ ]]

[ ] [ [ ]]

U U x U U x U U x

U U x U U x

↔ ∨ ¬ = ¬ ∨ ∨ ¬ ∧ ∨ ¬ ∨ ¬

= ¬ ∨ ∨ ¬ ∧ ∨ ¬ ∧

6/14 From the construction of F₁

(1) F₁ is never true unless each U_iis V_i(x₁, x₂, x₃)．

(2) If each U_iis V_i(x₁, x₂, x₃)，we have F₁＝E₁ The above properties are proved by using induction．

proof is omitted．

Conversion to 3SAT form a b = a b

a b = (a b) (b a) = [ a b] [ b a]: useful relations

→ ¬

¬ ¬

↔ → ∧ → ∧

∨ ∨ ∨

1 2 3 1 2 3 1 2 2

1 2 3 1 2 2

[ ] [ ] [ [ ]]

[ ] [ [ ]]

U U x U U x U U x

U U x U U x

↔ ∨ ¬ = ¬ ∨ ∨ ¬ ∧ ∨ ¬ ∨ ¬

= ¬ ∨ ∨ ¬ ∧ ∨ ¬ ∧

6/14

6.2. 多項式時間還元可能性に基づく完全性 6.2.1. 完全性の定義とその基本的性質

定義6.2:計算量クラスCに対し，集合Aが次の条件を満たすとき，

それを（ の下で）C-完全という．

(a) L C[L A]

(b) A C

補注：条件(a)を満たす集合はC-困難．

P

≤m

∀ ∈ ≤^P_m

∈

7/14

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，if a set Asatisfies the following conditions, then it is called C-complete(under )

(a) L C[L A]

(b) A C

Note：Sets satisfying the condition (a) are called C-hard．

P

≤m

∀ ^∈ ≤^P_m

∈

7/14

6.2. 多項式時間還元可能性に基づく完全性 6.2.1. 完全性の定義とその基本的性質

例6.5.クラスNPの完全集合の例

3SAT, SAT, ExSAT, DHAM, KNAP, BIN, VCなど クラスEXPの完全集合

EVAL-IN-E, HALT-IN-Eなど

8/14

? ) 2 , , ( :

0 , , 1

:

, , :

: E - IN - EVAL

*

accept x

a me eval-in-ti

t x a

t x a

t =

≥ Σ

∈

>

<

出力

ド 入力プログラムのコー 入力

6.2.Completeness based on Polynomial-time Reducibility 6.2.1. Definition of Completeness and its Basic Properties

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.

8/14

? ) 2 , , ( :

Output

0 , , input 1 with program a of code the :

, , : Input

: E - IN - EVAL

*

accept x

a me eval-in-ti

t x a

t x a

t =

≥ Σ

∈

>

<

定理6.3.任意のC-困難集合（含：C-完全集合）Aに対し，

(1) A PÆC⊆P 対偶はC P ÆA P

(2) A NPÆC⊆NP 対偶はC NP ÆA NP

(3) A co-NP ÆC⊆co-NP 対偶はC co-NP ÆA co-NP

(4) A EXPÆC⊆EXP 対偶はC EXP ÆA EXP

∈

∈

∈

∈

∉

∉ ∉

∉

⊄

⊄⊄

⊄ 証明：

(1) Bを任意のC集合とすると，AはC-困難だから，

A

B≤^P_m 一方，A Pの仮定より，B P（定理6.1）

(2), (3), (4)も同様

∈ ∈

9/14

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

(1) A PÆC⊆P CP: C P ÆA P

(2) A NPÆC⊆NP CP: C NP ÆA NP

(3) A co-NP ÆC⊆co-NP CP: C co-NP ÆA co-NP (4) A EXPÆC⊆EXP CP: C EXP ÆA EXP

∈

∈

∈∈

∉∉

∉∉

⊄

⊄⊄

⊄

Proof： CP: contraposition

(1) LetBbe any C-set. Then, since Ais C-hard, A

B≤_m^P and by the assumption A Pwe haveB P（Th. 6.1）

(2), (3), (4) are similar.

∈ ∈

9/14

例6.6.定理6.3の意味（クラスNP) AをNP-完全集合とする．

定理6.3(1)の対偶より，

NP PÎA P

定理6.3(3)の対偶と定理5.9(1)の対偶より，

A co-NP

つまり，NP-完全集合はP NPである限り，

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

∉

≠ ∉

≠

10/14

定理5.9.

(1) NP⊆co-NPÆNP= co-NP 定理6.3.任意のC-困難集合（含：C-完全集合）Aに対し，

(1) A PÆC⊆P 対偶はC P ÆA P

(2) A NPÆC⊆NP 対偶はC NP ÆA NP

(3) A co-NP ÆC⊆co-NP 対偶はC co-NP ÆA co-NP

(4) A EXPÆC⊆EXP 対偶はC EXP ÆA EXP

∈

∈

∈

∈

∉

∉ ∉

∉

⊄

⊄⊄

⊄

Ex.6.6:Meaning of Theorem 6.3（class NP) Let Abe NP-complete set．

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，NP-complete sets are NP-sets that cannot be recognized in polynomial time unless P= NP.

∉

≠ ∉

10/14

Theorem 5.9.

(1) NP⊆co-NPÆNP= co-NP Theorem 6.3.For any C-hard (or C-complete) set A，

(1) A PÆC⊆P CP: C P ÆA P

(2) A NPÆC⊆NP CP: C NP ÆA NP

(3) A co-NP ÆC⊆co-NP CP: C co-NP ÆA co-NP (4) A EXPÆC⊆EXP CP: C EXP ÆA EXP

∈

∈

∈∈

∉∉

∉∉

⊄⊄

⊄⊄

NP-完全集合はP NPである限り，NP co-NPには入らない NP集合である．

≠ ∩

NP

P

co-NP

NP完全 co-NP完全

11/14

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

NP

P

co-NP

NP-complete co-NP-complete

11/14

例6.7.定理6.3の意味（クラスEXP) DをEXP-完全集合とする．

定理6.3(1)の対偶（C P ÆA P, ここではEXP P ÆD P) P EXPÆEXP P ( P⊆EXP) ÆD P

定理6.3(2)の対偶（C NPÆA NP,

ここではEXP NP ÆD NP) NP EXP ÆEXP NP ( NP⊆EXP) ÆD NP 定理6.3(3)の対偶（C co-NP ÆA co-NP,

ここではEXP co-NP ÆD co-NP)

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

ところが定理5.7から であるから，D P.

⊄ ⊄

⊄

⊄ ⊄

⊄

∉ ∉

∉ ∉

∉ ∉

∉

∉ ∉

≠

≠

≠

⊄ ⊄

⊄ ^∴ ∉

∴

12/14

y P EXP

Ex. 6.7.Meaning of Theorem 6.3（class EXP) Let Dbe an EXP-complete set．

Contraposition of Theorem 6.3(1)

（C P ÆA P, where EXP P ÆD P) P EXP ÆEXP P( P⊆EXP) ÆD P Contraposition of Theorem 6.3(2)（C NPÆA NP,

Here, EXP NP ÆD NP) NP EXP ÆEXP NP ( NP⊆EXP) ÆD NP Contraposition of Theorem 6.3(3)（C co-NP ÆA co-NP,

here, EXP co-NP ÆD co-NP)

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

⊄ ⊄

⊄

⊄ ⊄

⊄

∉ ∉

∉ ∉

∉ ∉

∉ ∉

≠

≠

≠

⊄

⊄

∉

∴ ⊄

∴

12/14

定理6.4.A: 任意のC-完全集合 すべての集合Bに対し，

(1) A BÆBはC-困難．

(2) A B B CÆBはC-完全．

P

≤m P

≤m ∧ ∈ 証明：

定義6.2より，

定理6.2より，

したがって，

すなわち，BはC-困難．

[ ]

[ ]

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 Bwe have (1) A BÆBis C-hard.

(2) A B B CÆBis C-complete．

P

≤m P

≤m ∧ ∈ Proof：

By Def. 6.2 By Theorem 6.2，

Therefore，

That is，Bis C-hard．

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はEXP-完全}

NPC {L: LはNP-完全}

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

≡≡

定理6.5.

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

EXP EXPC

P 定理6.6: P NPを仮定すると

(1) NPC P= φ (2) NP– (NPC P) φ

∩

∪ ≠

≠

NP

NPC

P

NP∩co-NP

}

14/14

EXPC {L: Lis EXP-complete}

NPC {L:Lis 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

残りの予定(Schedule)

• 4/24 (Thu):

–レポートの回収(report submission)

• 4/24 Office Hour:

–レポートの解答と解説(Answers and comments for the report)

• 4/28:

休講

• 5/1:

中間試験

–持ち込み不可(No text, No notes, …)