岩田 茂樹
| 名誉教授・その他関係者 | 名誉教授 |
研究者情報
委員歴
- 2006年05月 - 2012年05月
編集顧問, 電子情報通信学会, 学協会 - 2007年05月 - 2009年05月
情報システムソサイエテイ副会長(編集担当）, 電子情報通信学会, 学協会 - 2004年05月 - 2006年05月
情報システムソサイエティ和文論文誌編集委員会委員長, 電子情報通信学会, 学協会 - 2003年05月 - 2004年05月
情報システムソサイエティ和文論文誌編集委員会副委員長, 電子情報通信学会, 学協会 - 2000年05月 - 2004年05月
情報システムソサイエティ和文論文誌編集委員, 電子情報通信学会, 学協会 - 2002年05月 - 2003年05月
情報システムソサイエティ和文論文誌編集委員会幹事, 電子情報通信学会, 学協会
研究活動情報
論文
- Shikaku and Ripple Effect are NP-Complete
Yasuhiko Takenaga; Shintaro Aoyagi; Shigeki Iwata; Takumi Kasai
Congressus Numerantium, 216巻, 掲載ページ 119-127, 出版日 2013年12月, 査読付
研究論文（学術雑誌）, 英語 - NP-completeness of Two Pencil Puzzles: Yajilin and Country Road
Ayaka Ishibashi; Yuichi Sato; Shigeki Iwata
UTILITAS MATHEMATICA, UTIL MATH PUBL INC, 88巻, 掲載ページ 237-246, 出版日 2012年07月, 査読付, Two pencil puzzles, Yajilin and Country Road, are shown NP-complete. Modified versions of the Hamiltonian cycle problem on planar undirected graphs are reduced to the puzzle problems to show NP-hardness.
研究論文（学術雑誌）, 英語 - Posets with seven linear extensions sortable by three comparisons
Satoshi Hanamura; Shigeki Iwata
INFORMATION PROCESSING LETTERS, ELSEVIER SCIENCE BV, 111巻, 8号, 掲載ページ 365-369, 出版日 2011年03月, 査読付, If every relation in a partial order also holds in a total order, then the total order is called linear extension of the partial order. The number of linear extensions is closely related with the number of minimum comparisons to sort the poset (D.E. Knuth, Sorting and Searching, 2nd ed., The Art of Computer Programming, Addison-Wesley, Reading, MA, 1998) [5]. We show that three comparisons suffice to sort any poset having seven linear extensions, and this result may speed up exhaustive computation to derive the lower bound of the minimum number of comparisons in sorting. (C) 2011 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - Three comparisons sufficient to sort posets with seven linear extentions
Satoshi Hanamura; Shigeki Iwata
Proc. of the 13th Japan-Korea Joint Workshop on Algorithms and Computation, 掲載ページ 110-115, 出版日 2010年07月, 査読付
研究論文（国際会議プロシーディングス）, 英語 - STONEHENGE: OUTCOME OF ALL FIRST MOVES AND PSPACE-COMPLETENESS
Yasuhiko Takenaga; Hikari Mori; Shigeki Iwata
ICGA JOURNAL, UNIV MAASTRICHT FACULTY GENERAL SCIENCES, 33巻, 1号, 掲載ページ 34-41, 出版日 2010年03月, 査読付, Stonehenge is a two-player game in which players alternately place a piece on an intersection of the lines drawn on the game board. The player who dominates more than half of the lines wins the game. In this note, we first present the result of exhaustive computations of Stonehenge: for all first moves, the winner of the game is computed, and the results show that the first player has a winning strategy. Second, we consider Generalized Stonehenge played on a hypergraph and prove its PSPACE-completeness.
研究論文（学術雑誌）, 英語 - Horn functions with a single two-negated term
N Kawamura; S Iwata
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E88A巻, 11号, 掲載ページ 3264-3266, 出版日 2005年11月, 査読付, Horn functions are Boolean functions where each of the prime implicants contains at most one negative literal. A class of Boolean functions is considered in this letter where a single term containing two negative literals is added by logical-or operation to a Horn function. We show that the function does not have any prime implicant containing three negative literals. We also show that if two terms containing two negative literals are added to a Horn function, then it may have many prime implicants all of which contain three negative literals. We show that it is P-complete to determine whether a given Boolean function in disjunctive normal form of the considered class is a tautology.
研究論文（学術雑誌）, 英語 - Some minimum merging networks
G Morohashi; S Iwata
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 329巻, 1-3号, 掲載ページ 237-250, 出版日 2004年12月, 査読付, Let M(m, n) be the minimum number of comparators which constructs an (m, n)-merging network. Batcher's odd-even merge, which is a merging network constructed by his algorithm, provides the best upper bound for M(m, n) to date. Recently Iwata (Inform. and Comput. 168 (2001) 187) analyzed the property of leftmost comparators, and showed M(m(1) + m(2), n) greater than or equal to [ (M(m(1), n) + M(m(2), n) + m(1) + m(2) + n - 2)/2]. We extend Iwata's proofs and show that Batcher's (6, 8k + 7)-, (9, 16k + 9)-, (7, 8) -merging networks are optimal for all k greater than or equal to 0.
In Batcher's (m, n)-merging network, the ith smallest element out of m elements and another ith smallest element out of n elements are first compared for all i(1 less than or equal to i less than or equal to min{m, n}). Under an assumption of existence of such min{m, n} comparators in optimal (m, n)-merging networks, we show that M(n, n) = M(n - 1, n) + 1 = M(n - 2, n) + 3. (C) 2004 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - 一般化ブロックパズルの PSPACE 完全性の別証明
北川智博; 岩田茂樹
京都大学数理解析研究所講究録, 1325巻, 掲載ページ 209-214, 出版日 2003年05月
研究論文（大学，研究機関等紀要）, 日本語 - Some minimum merging networks
Gembu Morohashi; Shigeki Iwata
33rd Southeastern Conference on Combinatorics, Graph Theory, and Computing, 77号, 出版日 2002年03月, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Lower bounds for merging networks
S Iwata
INFORMATION AND COMPUTATION, ACADEMIC PRESS INC, 168巻, 2号, 掲載ページ 187-195, 出版日 2001年08月, 査読付, A lower bound theorem is established for the number of comparators in a merging network. Let M(m, n) be the least number of comparators required in the (m, n)-merging networks, and let C(m, n) be the number of comparators in Batcher's (m, n)-merging network, respectively. We prove for n greater than or equal to I that M(4, n) = C(4, n) for n equivalent to 0, 1, 3 mod 4, M(4, n) greater than or equal to C(4, n) - 1 for n equivalent to 2 mod 4, and M(5, n) = C(5, n) for n equivalent to 0, 1, 5 mod 8. Furthermore Batcher's (6, 8k+6)-. (7, 8k +7)-, and (8, 8k+8)-merging networks are optimal for k greater than or equal to 0. Our lower bound for (m, n)-merging networks, m less than or equal to n, has the same terms as C(m, n) has as far as n is concerned. Thus Batcher's (m, n)-merging network is optimal up to a constant number of comparators, where the constant depends only on m. An open problem posed by Yao and Yao (Lower bounds on merging networks, J. Assoc. Comput. Mach, 23, 566-57 1) is solved: lim(n --> infinity) M(m, n)/n = [log m]/2 + m/2([log m]). (C) 2001 Academic Press.
研究論文（学術雑誌）, 英語 - 一般化詰将棋問題の指数時間完全性
横田雅也; 築地立家; 北川智博; 諸橋玄武; 岩田茂樹
電子情報通信学会論文誌, J84-D-I巻, 3号, 掲載ページ 239-246, 出版日 2001年03月, 査読付
研究論文（学術雑誌）, 日本語 - Minimum number of comparators in (6,6)-merging network
Koichi Yamazaki; Hibiki Mizuno; Kazuhisa Masuda; Shigeki Iwata
IEICE Trans. Inf. & Syst., E83-D巻, 2号, 掲載ページ 137-141, 出版日 2000年02月, 査読付
研究論文（学術雑誌）, 英語 - (4,7)-,(5,6)-マージングネットワークの最小比較器数のコンピュータによる計算
丹野岳久; 岩田茂樹
京都大学数理解析研究所講究録, 1054巻, 掲載ページ 40-53, 出版日 1998年07月
研究論文（大学，研究機関等紀要）, 日本語 - マージングネットワークの下界について
増田一寿; 岩田茂樹
電子情報通信学会論文誌, J80-D-I巻, 8号, 掲載ページ 665-673, 出版日 1997年08月, 査読付
研究論文（学術雑誌）, 日本語 - Some two-person game is complete for AC^k^ under many-one NC^1^ reducibility
Shigeki Iwata
IEICE Trans. Inf. & Syst., E77-D巻, 9号, 掲載ページ 1022-1026, 出版日 1994年09月, 査読付
研究論文（学術雑誌）, 英語 - Exhaustive computation to derive the lower bound for sorting 13 items
Shusaku Sawato; Takumi Kasai; Shigeki Iwata
IEICE Trans. Inf. & Syst., E77-D巻, 9号, 掲載ページ 1027-1031, 出版日 1994年09月, 査読付
研究論文（学術雑誌）, 英語 - THE OTHELLO GAME ON AN N X N BOARD IS PSPACE-COMPLETE
S IWATA; T KASAI
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 123巻, 2号, 掲載ページ 329-340, 出版日 1994年01月, 査読付, Given an arbitrary position of the Othello game played on an n x n board. the problem of determining the winner is shown to be PSPACE-complete. It can be reduced from generalized geography played on bipartite graphs with maximum degree 3.
研究論文（学術雑誌）, 英語 - Thirty four comparisons are required to sort 13 items
Takumi Kasai; Shusaku Sawato; Shigeki Iwata
Lecture Notes in Computer Science, Springer-Verlag, 792巻, 掲載ページ 260-269, 出版日 1994年, 査読付
研究論文（その他学術会議資料等）, 英語 - RELATIONS AMONG SIMULTANEOUS COMPLEXITY CLASSES OF NONDETERMINISTIC AND ALTERNATING TURING-MACHINES
S IWATA; T KASAI; E MORIYA
ACTA INFORMATICA, SPRINGER VERLAG, 30巻, 3号, 掲載ページ 267-278, 出版日 1993年05月, 査読付, Ruzzo [Tree-size bounded alternation, J. Comput. Syst. Sci. 21] introduced the notion of tree-size for alternating Turing machines (ATMs) and showed that it is a reasonable measure for classification of complexity classes. We establish in this paper that computations by tree-size and space simultaneously bounded ATMs roughly correspond to computations by time and space simultaneously bounded nondeterministic TMs (NTMs).
We also show that not every polynormal time bounded and sublinear space simultaneously bounded NTM can be simulated by any deterministic TM with a slightly increased time bound and a slightly decreased space bound simultaneously.
研究論文（学術雑誌）, 英語 - Some EXPTIME complete problems on context-free languages
Takumi Tasai; Shigeki Iwata
IEICE Trans. Inf. & Syst., E76-D巻, 3号, 掲載ページ 329-335, 出版日 1993年03月, 査読付
研究論文（学術雑誌）, 英語 - Simulations of Turning machines by 2NPDA and their applications to open problems
Shigeki Iwata; Takumi Kasai
Congressus Numerantium, 72巻, 掲載ページ 81-92, 出版日 1990年02月, 査読付
研究論文（学術雑誌）, 英語 - Generalized Hi-Q is NP-complete
Ryuhei Uehara; Shigeki Iwata
Trans. IEICE, 電子情報通信学会, E73巻, 2号, 掲載ページ 270-273, 出版日 1990年02月, 査読付, This paper deals with a popular puzzle known as Hi-Q. The puzzle is generalized: the board is extended to the size n × n, an initial position of the puzzle is given, and a place is given on which only one token is finally placed. The complexity of the generalized Hi-Q is proved NP-complete.
研究論文（学術雑誌）, 英語 - n×n盤面上の将棋の指数時間完全性について
安達博之; 亀川裕之; 岩田茂樹
電子情報通信学会論文誌, J70巻, 10号, 掲載ページ 1843-1852, 出版日 1987年10月, 査読付
研究論文（学術雑誌）, 日本語 - SIMULTANEOUS (POLY-TIME, LOG-SPACE) LOWER BOUNDS
S IWATA; T KASAI
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 54巻, 2-3号, 掲載ページ 325-329, 出版日 1987年, 査読付
研究論文（学術雑誌）, 英語 - Simple programs with a fixed number of variables seem still hard to analyze
Shigeki Iwata; Takumi Kasai
掲載ページ 405-416, 出版日 1987年, 査読付
英語 - A note on some simultaneous relations among time, space, and reversal for single work tape nondeterministic turing machines
Etsuro Moriya; Shigeki Iwata; Takumi Kasai
Information and Control, 70巻, 2-3号, 掲載ページ 179-185, 出版日 1986年, 査読付, Simultaneous resource bounded complexity classes for nondeterministic single worktape off-line Turing machines are considered such as time-space bounded classes, denoted by NTISP1(T, S), reversal-space bounded classes, denoted by NRESP1(R, S), and time-reversal bounded classes, denoted by NTIRE1(T, R). It is shown that NRESP1(R(n), S(n)) contains NTISP1(S(n), R(n)) and is contained in NTISP1(R(n) S(n)n2 log n, R(n) log n). The following corollaries follow: (1) the affirmative solution to the nondeterministic single worktape version of the NC = ? SC problem, NTIRE1(poly, polylog) = NTISP1(poly, polylog), and (2) a reversal-space trade-off, NRESP1(polylog, poly) = NRESP1(poly, polylog). © 1986 Academic Press, Inc. All rights reserved.
研究論文（学術雑誌）, 英語 - Gradually intractable problems and nondeterministic log-space
Takumi Kasai; Shigeki Iwata
Math. Systems Theory, 18巻, 掲載ページ 153-170, 出版日 1985年, 査読付
研究論文（学術雑誌）, 英語 - Problem requiring k log n deterministic space
Shigeki Iwata; Takumi Kasai
Congressus Numerantium, 44巻, 掲載ページ 161-174, 出版日 1984年12月, 査読付
研究論文（学術雑誌）, 英語 - Some combinatorial game problems require Ω(n^k^) time
Akeo Adachi; Shigeki Iwata; Takumi Kasai
J. of the Assoc. Comput. Mach., ASSOC COMPUTING MACHINERY, 31巻, 2号, 掲載ページ 361-376, 出版日 1984年, 査読付
研究論文（学術雑誌）, 英語 - Graph theoretic problems complete for nondeterministic log-space
Yoshiaki Fukazawa; Shigeki Iwata
Trans. IECE, E66巻, 2号, 掲載ページ 102-107, 出版日 1983年02月, 査読付
研究論文（学術雑誌）, 英語 - Low level complexity for combinatirial games
Akeo Adachi; Shigeki Iwata; Takumi Kasai
Proc. 13rd Ann. ACM Symp. on Theory of Computing, 掲載ページ 228-237, 出版日 1981年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Maximum number of prime implicants for a class of restricted boolean functions
Shigeki Iwata
Congressus Numerantium, 29巻, 掲載ページ 531-534, 出版日 1980年12月, 査読付
研究論文（学術雑誌）, 英語 - Satisfiability problems require exponential time for monadic predicate caliculus
Shigeki Iwata; Takumi Kasai
Proc. Fifth IBM Symp. on Math. Found. of Comput. Sci., 出版日 1980年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Classes of pebble games and complete problems
Takumi Kasai; Akeo Adachi; Shigeki Iwata
SIAM J. Comput., 8巻, 4号, 掲載ページ 574-586, 出版日 1979年11月, 査読付
研究論文（学術雑誌）, 英語 - Programs with minimal number of goto statements
Shigeki Iwata
Information and Control, 37巻, 1号, 掲載ページ 105-114, 出版日 1978年04月, 査読付
研究論文（学術雑誌）, 英語 - Classes of pebble games and complete problems
Takumi Kasai; Akeo Adachi; Shigeki Iwata
Proc. 1978 Ann. Conf. ACM 78, 掲載ページ 914-918, 出版日 1978年, 査読付
研究論文（国際会議プロシーディングス）, 英語
講演・口頭発表等
- 上書きハッシュ表の性質
山口陽平; 岩田茂樹
口頭発表（一般）, 日本語, 第12回情報科学技術フォーラム(FIT2013)
発表日 2013年09月 - ゲーム「ストーンヘンジ」の先手必勝性及びPSPACE完全性
森皓; 武永康彦; 岩田茂樹
口頭発表（一般）, 日本語, 電子情報通信学会,電子情報通信学会2009年総合大会
発表日 2009年03月 - 一般化美術館問題のNP完全性
浅田益仁; 岩田茂樹
口頭発表（一般）, 日本語, 電子情報通信学会,2006年電子情報通信学会総合大会
発表日 2006年03月 - 単一２負項を加えたホーン関数
川村直輝; 岩田茂樹
口頭発表（一般）, 日本語, 信学技報
発表日 2005年03月 - 一般化詰将棋問題の指数時間完全性について
横田雅也; 築地立家; 北川智博; 諸橋玄武; 岩田茂樹
口頭発表（一般）, 日本語, 電子情報通信学会技術研究報告
発表日 2000年10月 - (4,7)-マージングネットワークと(5,6)-マージングネットワークの最小比較器数について
丹野岳久; 岩田茂樹
口頭発表（一般）, 日本語, 電子情報通信学会技術研究報告
発表日 1997年12月 - マージングネットワークの下界の計算について
増田一寿; 岩田茂樹
口頭発表（一般）, 日本語, 電子情報通信学会技術研究報告
発表日 1996年09月 - マージングネットワークにおけるある下界について
水野 響; 増田一寿; 岩田茂樹
口頭発表（一般）, 日本語, 京都大学数理解析研究所講究録
発表日 1996年04月 - オセロゲームの複雑さ
岩田茂樹; 笠井琢美
口頭発表（一般）, 日本語, 電子情報通信学会技術研究報告
発表日 1993年09月 - Some problems in formal language theory known as decidable are preved EXPTIME complete
Takumi Kasai; Shigeki Iwata
口頭発表（一般）, 日本語, 京都大学数理解析研究所講究録
発表日 1992年07月 - 文脈自由言語と括弧言語に関する指数時間完全の問題
岩田茂樹; 笠井琢美
口頭発表（一般）, 日本語, 電子情報通信学会技術研究報告
発表日 1991年12月