計算の複雑性に関する研究

(1)

一 ilz6 t 〈 g -p v 一〇 rv

数理解析研究所講究録

381 計算の複雑性に関する研究

禁帯出期間

55e 5e 22

一一

5e 29

数研図書室

京都大学数理解析研究所

1980

年

4

月

/) _ノ、フん

(2)

RIMS Kafeyunolea 381

STUDIES ON

COIViPUTATIONAL COMPLEXITiES AND RELATED TOPICS

U sesS K ee

2704225 pt $

igcJgl jagiivMff lie i } sir

April, l980

Research Institute for Mathematical Sciences

Kyoto University, Kyoto, Japan

(3)

fliLof;l$/Si4N:ti · - · whgshq’3d7u-’

ptsB,.g;!, } ,#re4

i980 i4. 2n5 H – 2n7 B

m%’e¡9esL2a J7Ii”)ecPLjik.

g 7Aip

Z. Series of graphs generated by rational machines

A new developmental system .e..ee.e·.ee...e·.··. 1

ff/Jkk i9 N-

±

DfeXk9P

2. 0n forming a series-paralZel graph by removing nodes

of a pianar graph .···-···.·ee.ee·e·e···e··e··e·ee····22

2’‘),N”71¡k P 7.mS5ip.”

j5,51i;,i” ,X.! · i-

Nl7ir[¡’[l’ pZ

3. A fast aigorithm for cornputing the maximum number of

prime implicants of symmetric booiean functions ...42

24.%JK ; btvagK

”’ ’‘.-;i,2lli712211ri ji’laSf‘5’ji } FiNtiz):’!Iili- · /¿e/,jNlitfSll.liiE.(z)illElilllL.‘ts’ ””””e”””””52

vpm SlEJLik!i; Z,9, reJE mpj thtvp-x aKfaien

-i -”

(4)

5

6

7

8

9

IO

.

7” p tiN ii7 bN tSl) iS¡” i ”.. 21 s )’I Zk 7?ime L space ‘Z)

Trade-Off .··.e.··.··.·.··.·e·...e.e...·.·.·...

ft..Jkk:ka9di kithfr?l¡.

apt iBM ,VkVP%Z 1’,ffgJStlL?Attt3’;3’a)4’¡kx”e9’;;i,ci’el?i · e · e ···· e ··· e ··· ...

MitJk¡. gk;;h”a 7’Aigtiepjusl

jEl 3¿9 41 .i2,tiF D

A de?ivation of Cook’s simulation algorithm by program tranSfOrMatiOn ...ee....e.eeeeee...e..e...

xkt]¡ se- ’,AL. 7S

¡l(. } ilYi)- -(t;itf } el:1ifttliDptptbvpg’5 Lj;,LQr,;l,, } tS(sz-7 ” ( ··· e ··· e ·

,”t¿”N.iK,. 2i- iilliliilliNtil’lllll.,¡.

fi { .Iii4iJfni$Ni-!-

Complexity of some strategies proving theorems in the propositional logie ·..e..·.e.·.·...ee.e·.·...·.·.·.···

tf

5

￡ K x thJlt’af” il’2¿e

i.)p6k)Z-q

el } gfet ? Q!L k.. 1 ?vgl 3.z } ijl } tntg¿g } ,z) computationai

COMPIeXitY eeeee-ee”eeeee-eeeeeeeee-ee-eeeeeeeeeeeeete-

rnl.l2k tJ)¡y Ae”. is ;llii2. } di

9..Kikl2hfr ”M.,.f-edyX

tr

- ti -

.

.73

.85

c

IOO

li6

l33

l52

(5)

lle

12.

i3・

14.

15・

P

一・

(z,,.

ンタ紹顧おあびデータ変換疹こ蘭連し徐罵纐の

繍複換

. . .... . .

・

6

・

、広人二菊野喜

f

角

1

橡日月

知二一乃原一夫

An extended iteration statement and its computabi:Lity...180

東喬人握里下竹夫

づババノ

覆総勿サニ禾ノ男君日本工

BM

足

M2

一

多イ鍮理工の伽回雪傷

. .

・

95

霧叉木

1

記田元

配ヲヤフノレ飢た記号列乞入批フる

茄餓オート

Z

トγ

1

こついて・…・・…・………・・2・7

ネノ下人理下間一罐

京六二競

へ

1

司期づ牲叡システム

(SPS)IP

キロ・て・…………

223

名大エム下碓史

3

_{墜人工纐ッ亘康善}

名犬工

.

本多彼が昆

一i且一

(6)

・

6.k7

多

0

集勧縫ノ汐一ン豚め瑚題

1

匂て・…

242 簿切教育大呼ラ勃醐

京人エ

px

赫彦

・

7

・椀全才霰吻嫉データタイプ。の塀織娘実現…・

258 SP](

工飯勧菱樹

多重人エ彬坦彦善

名ノ

(

、エ本多疲本彦

一コV一

計算の複雑性に関する研究

一 ilz6 t 〈 g -p v 一〇 rv

381