Doctor of Engineering, Waseda University

combinatorial theory

complexity

algorithm

組合せ理論

計算量

アルゴリズム

Informatics, Information theory

Feb. 1980
Waseda University, Graduate School, Division of Science and Engineering, 電気工学専攻

Mar. 1973
Waseda University, Graduate School, Division of Science and Engineering, 電気工学専攻

Mar. 1971
Waseda University, Faculty of Science and Engineering, 電気工学科

May 2006 - May 2012
編集顧問, 電子情報通信学会

May 2007 - May 2009
情報システムソサイエテイ副会長(編集担当）, 電子情報通信学会

May 2004 - May 2006
情報システムソサイエティ和文論文誌編集委員会委員長, 電子情報通信学会

May 2003 - May 2004
情報システムソサイエティ和文論文誌編集委員会副委員長, 電子情報通信学会

May 2000 - May 2004
情報システムソサイエティ和文論文誌編集委員, 電子情報通信学会

May 2002 - May 2003
情報システムソサイエティ和文論文誌編集委員会幹事, 電子情報通信学会

Jul. 2009
電子情報通信学会
電子情報通信学会フェロー

Shikaku and Ripple Effect are NP-Complete
Yasuhiko Takenaga; Shintaro Aoyagi; Shigeki Iwata; Takumi Kasai
Congressus Numerantium, 216, 119-127, Dec. 2013

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, Jul. 2012, 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, Mar. 2011, 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, Jul. 2010

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, Mar. 2010, 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, Nov. 2005, 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, Dec. 2004, 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, May 2003

Some minimum merging networks
Gembu Morohashi; Shigeki Iwata
33rd Southeastern Conference on Combinatorics, Graph Theory, and Computing, 77, Mar. 2002

Lower bounds for merging networks
S Iwata
INFORMATION AND COMPUTATION, ACADEMIC PRESS INC, 168, 2, 187-195, Aug. 2001, 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, Mar. 2001

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, Feb. 2000

(4,7)-,(5,6)-マージングネットワークの最小比較器数のコンピュータによる計算
丹野岳久; 岩田茂樹
京都大学数理解析研究所講究録, 1054, 40-53, Jul. 1998

マージングネットワークの下界について
増田一寿; 岩田茂樹
電子情報通信学会論文誌, J80-D-I, 8, 665-673, Aug. 1997

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, Sep. 1994

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, Sep. 1994

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, Jan. 1994, 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, May 1993, 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, Mar. 1993

Simulations of Turning machines by 2NPDA and their applications to open problems
Shigeki Iwata; Takumi Kasai
Congressus Numerantium, 72, 81-92, Feb. 1990

Generalized Hi-Q is NP-complete
Ryuhei Uehara; Shigeki Iwata
Trans. IEICE, 電子情報通信学会, E73, 2, 270-273, Feb. 1990, 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, Oct. 1987

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, Dec. 1984

SOME COMBINATORIAL GAME PROBLEMS REQUIRE OMEGA(NK) TIME
A ADACHI; S IWATA; T KASAI
JOURNAL OF THE ACM, 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, Feb. 1983

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, Dec. 1980

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, Nov. 1979

Programs with minimal number of goto statements
Shigeki Iwata
Information and Control, 37, 1, 105-114, Apr. 1978

Classes of pebble games and complete problems
Takumi Kasai; Akeo Adachi; Shigeki Iwata
Proc. 1978 Ann. Conf. ACM 78, 914-918, 1978

NP完全問題入門
岩田茂樹
Japanese, 共立出版, May 1995

有限オートマトン入門
岩田茂樹; 笠井琢美
Japanese, 森北出版, May 1986

上書きハッシュ表の性質
山口陽平; 岩田茂樹
Oral presentation, Japanese, 第12回情報科学技術フォーラム(FIT2013)
Sep. 2013

ゲーム「ストーンヘンジ」の先手必勝性及びPSPACE完全性
森皓; 武永康彦; 岩田茂樹
Oral presentation, Japanese, 電子情報通信学会,電子情報通信学会2009年総合大会
Mar. 2009

一般化美術館問題のNP完全性
Masuhito Asada; Shigeki Iwata
Oral presentation, Japanese, 電子情報通信学会,2006年電子情報通信学会総合大会
Mar. 2006

単一２負項を加えたホーン関数
川村直輝; 岩田茂樹
Oral presentation, Japanese, 信学技報
Mar. 2005

一般化詰将棋問題の指数時間完全性について
横田雅也; 築地立家; 北川智博; 諸橋玄武; 岩田茂樹
Oral presentation, Japanese, 電子情報通信学会技術研究報告
Oct. 2000

(4,7)-マージングネットワークと(5,6)-マージングネットワークの最小比較器数について
丹野岳久; 岩田茂樹
Oral presentation, Japanese, 電子情報通信学会技術研究報告
Dec. 1997

マージングネットワークの下界の計算について
増田一寿; 岩田茂樹
Oral presentation, Japanese, 電子情報通信学会技術研究報告
Sep. 1996

マージングネットワークにおけるある下界について
水野 響; 増田一寿; 岩田茂樹
Oral presentation, Japanese, 京都大学数理解析研究所講究録
Apr. 1996

オセロゲームの複雑さ
岩田茂樹; 笠井琢美
Oral presentation, Japanese, 電子情報通信学会技術研究報告
Sep. 1993

Some problems in formal language theory known as decidable are preved EXPTIME complete
Takumi Kasai; Shigeki Iwata
Oral presentation, Japanese, 京都大学数理解析研究所講究録
Jul. 1992

文脈自由言語と括弧言語に関する指数時間完全の問題
岩田茂樹; 笠井琢美
Oral presentation, Japanese, 電子情報通信学会技術研究報告
Dec. 1991

ACM(Association for Computing Machinery)

EATCS(European Association for Theoretical Computer Science)

電子情報通信学会