京都大学数理解析研究所

数理解析研究所講究録 871

計 算 量 理 論

京都大学数理解析研究所

1994 年 5 月

計算量理論 研究集会報告集

1994年2月1日{}2˜ 月3日

研究代表者 丸岡 章(Akira Maruoka)

目 次

1 A Hierarchy Result of CoGperating Systems of Two-way

C e u R t e r Ma c h 1 n e s一一一一一一一 ・一d一一一一一 一一・ 一一 一一一 一一 一一 一一一 一一 一一 一・t一一 一・ 一一一一 一一一・一 一一 一一 ・一 一一 一一 一t一一一・一一 一一 一E一一 一一一 一一 一一一1

山回大工 王 躍 (Yue Wang)

山回大工 井上 克司 (Katsushi lnoue)

山回大・工 高浪 五男(ltsuo Takanami)

2 Seme Hterarchy Results ef Alternattng Finite Automata with

C c u R t e r s a n d S t a c k-C o u n t e r s一一一一 一一 一一 一・ 一一一一一 一一 一一一一 一一 一一一一 一一 一一一一一 一・d一 一一一一一一一一一一一i一一 一一t一B

徳山高専 義永 常宏(TSURehiro Yoshmaga)

二二大工 井上 克司(Katsushi lnoue)

山ロ大工 高浪 五男(ltsuo Takanami) 3 Optimal Simulatien of Twe一一Dimensional AlterRating Finite Automata

by Three・一Way Nondeterm E n i st i c Tur i ng Mach i nes一一 一一 一一一一一 一一 一一 一一 一一 一一一 一一 一一一一一 一一 一一 一一 一一一一一1 5 二二大工 伊藤 暁(Akira lte)

山回大工 井上 克司(Katsushi lnoue)

山回大工 高浪 五男(ltsue TakaRaml)

4

2 4

信州大工 山本 博章 (Hiroaki Yamamoto)

5 A Complexity Theoretic Approach te Breaking Cryptosystems Based

o n D i s c r e t e L o g a r t t hms一一 ・一 一一一一一 一・ 一一 一一一一 ・一 一一 ・一一一一一 一一・ 一一一一一 一一 一一一一 ・一 ・一 一一 一一一 一一 一一一一一一一一一 一一一2 9 九大工 櫻井 幸一(KOUIchl Sakurai)

東北大情報科学 静谷 啓樹(Hirokl Shizuya) 6 On a Method of Solving NP一一Complete Problems iR Polynomial Time

UsiRg the auantum TuriRg Machine一一一一一一一一一一一一一一一・一一一一一一一・一一一一一一一一一一一一一一一一一一一一一一一30 北陸先端科学技術大情報科学 三原 孝志(Takashi Mihara)

北陸先端科学技術大・情報科学 西野 哲朗(Tetsuro Nl sh mo)

7 木状 Haj6s Calculus の非多項式時間限定性一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一 37

九大工 岩間 一雄 (Kazuo lwama)

8

9 10

11

12

13

14

15

U R i q u e 1 y P a r s a b 1 e G r amma r s一一 一一 一p一 ・一 一・ 一一 一一 ・一 一一一 一一 一一一一一一一一 一一・ ・一 ・一一一 一一 ・一 一一・ ・一 一一 一一 一一・ 一一一一 一一 一一一一 一一一4 5 広島大工 森田 憲一(Kenichi Morita)

国立民族学博物館 山本 泰則(Yasunori Yamamoto) 山形大工 西原 典孝(Noritaka Nishihara) 山形大工 張 治国 (Zhiguo Zhang)

LOGICAL FORMULAS FOR PETRI NET co・一bLANGUAGES一一一一一一一一一一一一一一一一一一一一一一一一一一・一一一52

一橋大法 山崎 秀記(Hideki Yamasaki)

A GraPh Medlal Ax

s

ransform

59

Yarmouk Univ Taher Naser

朋治大・理工 中村 昭(Akira Nakamura)

1次元可逆セル・オートマトンにおける一斉射撃問題について一一一一一一一一・一一一一一66 広島大工 今井 開園 (Katsunobu lmal)

広島大工 森田 憲一(Kenich Morita) The Maximum Late cy aRd ldentification of Pesitive Boglean

F u n c t t o n s一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一 一一 一一一一一7 3 京大・工 牧野 和久(Kazuhisa Mak;no)

京大・工 茨木 俊秀 (丁oshthide lbaraki)

On the Cemputational Power of Binary Decision Diagram with

Re d u n d a R t Va r i a b 1 e s一一一一一 一一 一一一 一一 一一一 一・ 一一 一一 一一一 一一 一一 一一 一一 一一 一一一 一一 一一 一一 一一 一一 一・ 一一 一一一一一 一一一 一一一一・ 一一一一一一 一一一8〇 九大総合理工 山田 哲也(Tetsuya Yamada)

九大総合理工 安浦 寛人(Hirote Yasuura) On the Stze of Ordered Binary DecisioR Diagrams Representing

T h r e s h o 1 d F u n c t i o n s一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一・ 一一 一一 一一 一一一 一一一一一 一一一8 7 京大工 保坂 和寿(Kazuhisa Hosaka)

京大工 武永 康彦(YaSllhiko Takenaga) 京大工 矢島 脩三(Shuzo YaJlma)

否定数限定反転回路の複雑さの下界について一一一一一一一一一一一一一一一一一一一一一一一一一一一

9 4

北陸先端科学技術大情報科学 西野 哲朗(Tetsuro Nishino)

16 On the lmpertance ot Each Edge Using lts Traffec aleng Shertest

P a t h s i n a N e twg r k一一 一一一一一一一一一一一 一一 一t一一 一一一一一一一一 一一 一一 一一一一 一一 一一一一一一 一一 一一 一一一 一一 一一一一一一 一一一1 O O

豊橋技術科学大知識情報工学系 程 鵬(Peng Cheng)

豊橋技術科学大知識情報工学系 増山 繁(Shigeru Masuyama)

17 Efficient Aigorithms fer DisjoiRt Paths in Hypercubes

a n d S t a r N e two r k s一一一一一一 一一 一一一 一一 一一一一一一一一一一一 一一 一d一 ・一 一一一一一一一一 一・ 一一 一一 一一 一一 一一 一一 一一 一一一 一一 一一 一一一1 O 5

会津大 alan PIRg Gu

会津大 大川 知 (Sateshi Okawa)

会津大 Shletung Peng

18 SATへの変換を利用したグラフ問題の難しさの評価方法について一一一p一一一一一一一一112

九大工 宮崎 修一 (Shulchl Miyazaki) 九大工 岩間 一雄 (Kazuo Iwama)

19α連結成分問題の計算複雑さの上昇について一一一一一一一一一一一一一一一一一一一一一一一一一一一117 九大工 岩本 宙造(Chuze Iwamoto)

九大工 岩間 一雄(Kazuo lwama)

20 Randomized Algorithms for VariaRce-Based K-Clustering・一一一一一一一一一一一一一一一一一一124 東大理 稲葉真理(Mary lnaba)

神戸商科大管理 加藤 直樹(Naoki Katoh)

東大理 今井浩(H 置roshi lmal)

21 Simulating Fair Dice with a Small Set of Rationally Based Coins一一・一一一一13e 東工大総合理工学研究科 伊東 利哉(Toshtya ltoh)

東工大総合理工学研究科 望月 貴裕(Takahiro Mechiduki) 22 On Checkers, Self-Testers, and Self-Debuggers一一一一一一一一一一一一一一一一 一一一一一一一一一・一一一一一138

東工大総合理工学研究科 森 啓悦(Hlroyoshi Mori) 東工大総合理工学研究科 伊東 利哉(Toshiya ltoh)

23 LR 構文解析の並列アルゴリズムについて一一一一一一一・一・一一一一一一一一一一一一一一一一一一一一一一一一 145

豊橋技術科学大知識情報工学系 増山 繁(Shigeru Masuyama)

24 Findsng Maxtmal Cycle-Free Sets in Parallel

t

154

State Univ of New Yerk Xin He

2s EfficieRt Paraliel Shortest Path Algorithms for Banded Matrices 一一・一・一一一 161 Unlv ef Kentuckey

(Yljle Han)

群馬大工 五十嵐 善英 (Yoshihide lgaraski) 26 分散システムにおける資源割り当てアルゴリズムー一一一一一一一一一一一一一一一一一一一一 1 6 8

広大工 角川 裕次

(Hirotsugu Kakugawa)

広大工 宮本 英典(HideRori Miyameto) 広大工 角川 裕次(H置rgtsugu Kakugawa) 広大工 山下 雅史(Masafumi Yamashita)

28 Tight Bgund on the Competitive Ratio for the Page Replication

P r e b 1 em一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一1 8 2

Max-Planck-lnstitut Susanne Albers

東大理 古賀久志 (Hisashi Koga)

29遺伝アルゴリズムにおける交叉法に対する一考察一一一一一一一一一一一一一一一一一一一一一一190 京大工 柳浦 睦憲(Mutsunori Yagiura)

京大・工 茨木 俊秀(Toshihide lbaraki)

30 ハイパーグラフ分割問題に対する分散遺伝的アルゴリズムー一一一一一一一一一一一一一一一 197

広大工 若林 真一 (Shln lchl Wakabayashi) 31 LEARNING MONO丁ONE l OG-TERM DNF FORMULAS一一一一一一一一一一一一一一一一一一一一一一一一一一一一一204

東北大工 酒井 義文 (Yoshlfuml Sakal) 東北大・工 丸岡 章(Akira Marueka)

32非線形TRSのE重なり性判定問題について一一一一一一一一一一一一一一一一一一一一一一一一一一一一212 三重大工 松浦 邦博 (Kunihiro Matsuura)

三重大工 大山ロ 通夫(Mlchlo Oyarnaguchi) 三重大工 太田 義勝(Yoshikatsu Ohta)

33時間制約付LOTOSの等価性の証明一一一一一一一一一一一一一一一一一一i一 一一一一一一一・一一一一一一一一一一一一一一219 阪大・基礎工 中田 明夫(Aklo Nakata)

阪大基礎工 東野 輝夫(Teruo HigashiRO) 阪大・基礎工 谷ロ 健一(Kem ch i Taniguchi)

34『論語』における価値と感情の論理一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一226 日大理工 高橋 英之(Hideyuki Takahashi) 35 A Most Parsimonious Reconstruction Problem on Phylogenetic Trees一一一一一233

東海大理 成嶋弘 (Hlroshi Narushima)

36逆探索法を用いた正則単体分割の列挙一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一241 東大理学系研究科 正田 備也(Tomonari Masada)

37チェス盤上の配置問題について一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一248 茨城大教養 仙波 一郎(lchiro Semba)