計算量の理論

I216  計算量の理論と離散数学

上原隆平、面 和成

I216 Computational Complexity and

Discrete Mathematics

by 

Prof. Ryuhei Uehara and

Prof. Kazumasa Omote

計算量の理論

• ゴール1:

– “計算可能な関数_/問題_/言語_/集合_”

• ゴール2:

– 「問題の困難さ」を示す方法を学ぶ

• 計算可能な問題であっても、手におえない場合がある！

– 計算に必要な資源（時間・領域）が多すぎるとき

• 関連する専門用語;

クラスNP, P≠NP予想, NP困難性, 還元

Computational Complexity

• Goal 1:

– “Computable Function/Problem/Language/Set”

• Goal 2:

– How can you show “Difficulty of Problem”

• There are intractable problems even if they are  computable!

– because they require too many resources (time/space)!

• Technical terms;

The class NP, P≠NP conjecture, NP‐hardness, reduction

5.  計算量の理論

5.0. 概要

• 「計算可能」

計算にどのくらいの資源（コスト）が必要か？

– 計算量の理論

1. 計算量の上界の研究 2. 計算量の下界の研究

3. 計算の困難性の階層構造の研究

5. Computational Complexity

5.0. Overview

• “Computable?”

How much cost is required for computation?

– Computational Complexity Theory

1. Studies on upper bound of computational cost 2. Studies on lower bound of computational cost 3. Structural studies on hardness of computation

5. 計算量の理論

5.0.1. 計算量の上界の研究

アルゴリズム論: 効率の良いアルゴリズムの設計 – アルゴリズム A が問題 X を大きさ n のどんな

入力に対しても高々 T(n) 時間で解けるとする．

– このとき，アルゴリズム A の時間計算量の 上界は T(n) である．

[最悪な場合の漸近的な時間計算量]

5. Computational Complexity

5.0.1. Studies on upper bound of computational cost Algorithm Theory: design of efficient algorithms

– Suppose we have an algorithm A which solves a  problem X in at most time T(n) for any input of  size n.  

– Then, an upper bound on the time complexity of  the algorithm A is T(n).

[asymptotic worst case time complexity]

5. 計算量の理論

5.0.2. ^{計算量の下界の研究}

問題Ｘ に対するどんなアルゴリズムも最悪の場合

T(n) 時間かかるとき，問題Ｘ の時間計算量の下

界は T(n) である．

• P ≠NP 予想

• 暗号システムの頑健性

5.0.3. 計算の困難性の階層構造の研究

問題の困難性に関する概念「xx困難性」の階層構 造の特徴付けを研究する

5. Computational Complexity

5.0.2. Studies on lower bound of computational cost If any algorithm for a problem X takes time T(n) in 

the worst case, a lower bound on the time  complexity of the problem X is T(n).

• P ≠NP conjecture

• Robustness of crypto system

5.0.3. Structural studies on hardness of computation Studies to characterize hardness in the level of “xx‐

hardness” hierarchical structure depending on the  hardness

5. 計算量の理論

5.1. ^{計算時間の評価}

定義: どんな入力に対しても停止する(決定性)チューリングマシンをMとす る．このときMの実行時間または時間計算量は以下を満たす関数 f:→ である：.

このとき，

•Mの実行時間は f(n)時間

•Mはf(n)時間チューリングマシンという [注意]

• f(n) は長さnの文字列すべてに対する最大値をとっている (最悪の場合の実行時間)

• 通常， f(n) は単調増加関数だが…? 

アルゴリズムを評価/比較するため にはさらなる道具が必要．

5.1.1. チューリングマシンの時間計算量

f(n) は長さnのすべての入力xに対するM(x)のステップ数の最大値

5. Computational Complexity

5.1. Measuring Computation Time

Definition:

Let M be a (deterministic) Turing machine that halts on all inputs.

The running time or time complexity of M is the function f:→ s.t.

f(n) is the maximum number of steps of M(x) for all x of length n In the case, 

• we say that M runs in time f(n)

• M is an f(n) time Turing machine [Note]

• f(n) takes the maximum for all strings of length n (worst case complexity)

• usually, f(n) may be monotone increasing function, but…? 

We need further tools to  estimate/compare algorithms 5.1.1. Time complexity of a Turing machine

5. 計算量の理論

5.1.計算時間の評価

定義: 自然数上の関数 f と g に対し，

ヨc,n₀ >0, ∀n≧n₀ [f(n)≦ c g(n)]

が成立するなら，f(n) は オーダー g(n) の関数といい，f(n) = O(g(n)) と書く．

例1: 自然数上の任意の関数 f, g, h に対して以下が成立: 1. ∀n[ f(n) ≦ g(n)]  f(n) = O(g(n)) 

2. [ f(n) = O(g) and g(n) = O(h(n))]  f(n) = O(h(n))

注意: 定数 c とn₀ はn とは独立に決められる必要がある．

例2: 以下を示せ: 1. 5n³+4n²+n=O(n³) 2. 5n³+4n²+n=O(n⁴) 3. 5n³+4n²+n≠O(n²)

[コメント] f(n)∈O(g(n)) と書く人もいる 5.1.2. O記法

5. Computational Complexity

5.1. Measuring Computation Time

Definition: For functions f and g on natural numbers, if  ヨc,n₀ >0, ∀n≧n₀ [f(n)≦ c g(n)]

then we say f(n) is in the order of g(n) and denote it by f(n) = O(g(n)).

Ex. 1: The followings hold for any functions f, g and h on natural numbers:

1. ∀n[ f(n) ≦ g(n)]  f(n) = O(g(n)) 

2. [ f(n) = O(g) and g(n) = O(h(n))]  f(n) = O(h(n))

Remark: the constants c and n₀ must be determined independently of n.

Ex. 2: Prove the following:

1. 5n³+4n²+n=O(n³) 2. 5n³+4n²+n=O(n⁴) 3. 5n³+4n²+n≠O(n²)

[Comment] Some people write as f(n)∈O(g(n)) 5.1.2. Big‐O notation

5. 計算量の理論

5.1.計算時間の評価

定義: を計算問題，f(n) を自然数上の関数とする．

 を計算するプログラムA が f(n) 時間で動作して以下を満たすとする．

ヨc, n₀>0, ∀n≧n₀ [ f(n)≦ c g(n)]

このとき  は O(f(n)) 時間で計算可能，または の時間計算量はO(f(n))である．

5.1.3. 問題の時間計算量

直観的には，

「問題  が f(n)時間で計算可能」というとき，

・ Aの時間計算量はf(n)より小さいかもしれない

・ Aよりも速く を計算するアルゴリズムがあるかもしれない 問題の複雑さに関する上界を与えているにすぎない

解析を改善できるかもしれない

より速いアルゴリズムが 見つかるかもしれない 注意: 定数 c と n₀ はn とは独立に決められる必要がある．

5. Computational Complexity

5.1. Measuring Computation Time

Definition: Let  be a computing problem and f(n) be a function over natural  numbers. If we have a program A to compute  that runs in time f(n) such that

ヨc, n₀>0, ∀n≧n₀ [ f(n)≦ c g(n)]

then we say that  is computable in O(f(n)) time, or time complexity of  is O(f(n)).

Remark: the constants c and n₀ must be determined independently of n.

5.1.3. Time complexity of a problem

Intuitively,

“problem is computable within time f(n)” means

・ time complexity of Amay be less than f(n).

・ there may be a faster program to compute  than Adoes.

It only gives an upper bound of the complexity of the problem.

Our analysis may be improved

Better algorithm may be found

5.*. 素数判定問題の歴史



program Naive(input n);

begin

for each i:= 1 < i < n do

if n mod i = 0 then reject end‐if end‐for;

accept end.

log n・log i time

2～n‐1までのすべての数で実際に割ってみる

自然数 n を表現した文字列の長さをl とすると，l はおおよそ log nである．

したがって実行時間はO(l²2^l) である．

よって PRIME の時間計算量は O(l²2^l).である．

1 ( log log )

i n c n i d





) ) (log (

! log

log n n dn O n n ²

c  



時間アルゴリズムが 2002) 年に開発された!!

(l⁶ O

スターリングの公式：

n

e n n

n 



 



 2π 

!

PRIME

入力：自然数 n (2進数で表現) 質問:  n は素数か？

PRIME      {n : n は素数}={2,3,5,7,11,13,17,…}

実行時間

5.*. A history of the PRIME problem 



program Naive(input n);

begin

for each i:= 1 < i < n do

if n mod i = 0 then reject end‐if end‐for;

accept end.

log n・log i time

try to divide by numbers between 2～n‐1

When the length of n is l, l is approximately log n. So, the running time is O(l²2^l). 

Thus, time complexity of PRIME is O(l²2^l).

1 ( log log )

i n c n i d





) ) (log (

! log

log n n dn O n n ²

c  



time algorithm was  developed in 2002!!

) (l⁶ O

Stirling’s Formula：

n

e n n

n 



 



 2π 

!

PRIME

Input：a natural number n (binary representation) Question: Is n prime?

PRIME      {n : n is prime}={2,3,5,7,11,13,17,…}

running time

5. 計算量の理論

5.1.計算時間の評価

定義: 自然数上の関数 t(n) に対して，時間計算量 O(t(n)) の 集合(認識問題)全体の集合を O(t(n))時間計算量クラス

とよび，TIME(t(n)) とかく．こうした関数 t(n) は制限時間と呼ぶ．

5.1.3.問題の時間計算量

例1 PRIME は TIME(n²2ⁿ) の要素であったが 今は TIME(n⁶) の要素．

n n²

n⁶ 2ⁿ n²2ⁿ

×

×

多項式時間 指数時間

5. Computational Complexity

5.1. Time Complexity Classes

Definition: For a function t(n) over natural numbers, the set of all sets  (i.e. recognition problems) with time complexities O(t(n)) is 

called O(t(n))‐time complexity class, and it is denoted by TIME(t(n)).

Such a function t(n) is called a time limit.  

5.1.3. Time complexity of a problem

Ex. 1 PRIME was in TIME(n²2ⁿ),  but now it is in TIME(n⁶).

n n²

n⁶ 2ⁿ n²2ⁿ

×

×

Polynomial Exponential

5. 計算量の理論

5.2. 代表的な時間計算量クラス

5.2.2. 代表的な問題とその計算量

5.2.2.1. 命題論理式の評価 (PROP‐EVAL) 入力：<F, < a₁, a₂, … , a_n >> 

・F は拡張命題論理式

・ (a₁, a₂, … , a_n )は F への真偽値割当て 質問： F(a₁, a₂, … , a_n ) =1?

(x,y)

x→y (￢x∨y)

x y

((x→y)∧(y→x))

(0,0) 1 1

(0,1) 1 0

(1,0) 0 0

(1,1) 1 1



5. Computational Complexity

5.2. Representative Time Complexity Classes

5.2.2. Representative problems and their complexity

5.2.2.1. Problem of evaluating propositional expression(PROP‐EVAL) Input：<F, < a₁, a₂, … , a_n >> 

・F is an extended propositional expression

・ (a₁, a₂, … , a_n ) is a truth assignment to F Question： F(a₁, a₂, … , a_n ) =1?

(x,y)

x→y (￢x∨y)

x y

((x→y)∧(y→x))

(0,0) 1 1

(0,1) 1 0

(1,0) 0 0

(1,1) 1 1



5. 計算量の理論

5.2.代表的な時間計算量クラス

5.2.2.代表的な問題とその計算量

5.2.2.1.命題論理式の評価(PROP‐EVAL) 入力：<F, < a₁, a₂, … , a_n >> 

・F は拡張命題論理式

・(a₁, a₂, … , a_n )は F への真偽値割当て 質問： F(a₁, a₂, … , a_n ) =1?

F のコードから計算木を作る．

構築に必要な時間は O(|F|³).

ひとたび計算木ができると，

ボトムアップに計算すると

F(a₁, a₂, … , a_n ) の値は簡単に求まる．

Ex.： F(x₁, x₂ , x₃) = [x₁ ^ x₂]    [x₁^ x₃]



 ^



x₁ x₂ x₃

計算木 PROP‐EVAL ∈ P

F(0,1,0)=1

0 1 0

0

0 1

1

F(1,1,0)=0

1

1 0

0

0 0

0

5. Computational Complexity

5.2. Representative Time Complexity Classes

5.2.2. Representative problems and their complexity

5.2.2.1. Problem of evaluating propositional expression (PROP‐EVAL) Input：<F, < a₁, a₂, … , a_n >> 

・F is an extended prop. expression

・(a₁, a₂, … , a_n ) is a truth assignment to F Question： F(a₁, a₂, … , a_n ) =1?

Construct a computation tree from a code of F.

It is built in time O(|F|³).

Once computation tree is built,  we can easily obtain the value 

F(a₁, a₂, … , a_n ) in a bottom‐up fashion.

Ex.： F(x₁, x₂ , x₃) = [x₁ ^ x₂]    [x₁^ x₃]



 ^



x₁ x₂ x₃

computation tree PROP‐EVAL ∈ P

F(0,1,0)=1

0 1 0

0

0 1

1

F(1,1,0)=0

1

1 0

0

0 0

0

5. 計算量の理論

5.2.代表的な時間計算量クラス

5.2.2.代表的な問題とその計算量

5.2.2.2. 充足可能性 (SAT)

入力：<F> F は 2‐和積標準形

質問： F(a₁, a₂, … , a_n ) = 1とする真偽値割当てが存在するか？

和積標準形 (CNF)

F = (●∨●∨…∨●)∧(●∨…∨●)∧…∧(…)

‐ リテラルの∨の∧で表現される式

k SAT: 各項が k 個のリテラルを含む

3SAT, 4SATも同様に定義できる．

SAT は任意の CNF を許す

ExSAT は拡張命題論理式（∨,∧,→,  ）を許す

ちょうど/たかだか



5. Computational Complexity

5.2. Representative Time Complexity Classes

5.2.2. Representative problems and their complexity

5.2.2.2. Satisfiability (SAT)

Input：<F> F is 2‐conjunctive normal form       Question： Is there any assignment such that F(a₁, a₂, … , a_n ) = 1?

Conjunctive Normal Form (CNF)

F = (●∨●∨…∨●)∧(●∨…∨●)∧…∧(…)

‐ described by ∧ of ∨ of literals.

k SAT: Each closure contains k literals We can define 3SAT, 4SAT similarly.

SAT consists of any CNF.

ExSAT consists of any extended propositional expression.

exactly/at most

5. 計算量の理論

5.2.代表的な時間計算量クラス

5.2.2.代表的な問題とその計算量

5.2.2.3. グラフの到達可能性問題 (ST‐CON)

入力：<G,s,t> : 無向グラフ G, 1≦s,t≦n(=|G|) 質問： G は s から t への経路を持つか？

閉路とは両端点を共有する経路．

オイラー閉路とはすべての辺をちょうど一回通る閉路．

ハミルトン閉路とはすべての頂点をちょうど一回通る閉路．

5.2.2.4. オイラー閉路問題 (DEULER) 入力：<G>: 有向グラフ G

質問： G はオイラー閉路を持つか？

5.2.2.5 ハミルトン閉路問題 (DHAM) 入力：<G>: 有向グラフG

質問： G はハミルトン閉路を持つか？

実際には，

有向/無向 閉路/パス

という違いは問題にならない

5. Computational Complexity

5.2. Representative Time Complexity Classes

5.2.2. Representative problems and their complexity

5.2.2.3. Graph reachability problem (ST‐CON)

Input：<G,s,t> : an undirectd graph G, 1≦s,t≦n(=|G|) Question： Does G have a path from s to t?

Cycle is a path that shares two endpoints.

Euler cycle is a cycle that visits all edges once.

Hamiltonian cycle is a cycle that visits all vertices once.

5.2.2.4. Euler cycle problem (DEULER) Input：<G>: a directed graph G

Question： Does G have an Euler cycle?

5.2.2.5 Hamiltonian cycle problem (DHAM) Input：<G>: a directed graph G

Question： Does G have a Hamiltonian cycle?    

Actually,

directed/undirected cycle/path

do not matter

5. 計算量の理論

5.2.代表的な時間計算量クラス

5.2.2.代表的な問題とその計算量

以下は既知：

以下の問題は P の要素：

PROP‐EVAL, 2SAT, ST‐CON, DEULER

以下の問題は  の要素だが…

3SAT, DHAM

P と  の間(?)にあるクラスNP

5. Computational Complexity

5.2. Representative Time Complexity Classes

5.2.2. Representative problems and their complexity

It is known that：

The following problems are in P：

PROP‐EVAL, 2SAT, ST‐CON, DEULER

The following problems are in , but…

3SAT, DHAM

The class NP between P and ?