IWATA SHIGEKI
| Emeritus Professor etc. | Emeritus Professor |
Researcher Information
Educational Background
Member History
- May 2006 - May 2012
編集顧問, 電子情報通信学会, Society - May 2007 - May 2009
情報システムソサイエテイ副会長(編集担当）, 電子情報通信学会, Society - May 2004 - May 2006
情報システムソサイエティ和文論文誌編集委員会委員長, 電子情報通信学会, Society - May 2003 - May 2004
情報システムソサイエティ和文論文誌編集委員会副委員長, 電子情報通信学会, Society - May 2000 - May 2004
情報システムソサイエティ和文論文誌編集委員, 電子情報通信学会, Society - May 2002 - May 2003
情報システムソサイエティ和文論文誌編集委員会幹事, 電子情報通信学会, Society
Research Activity Information
Paper
- Shikaku and Ripple Effect are NP-Complete
Yasuhiko Takenaga; Shintaro Aoyagi; Shigeki Iwata; Takumi Kasai
Congressus Numerantium, 216, 119-127, Dec. 2013, Peer-reviwed
Scientific journal, English - 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, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed, 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.
Scientific journal, English - Some minimum merging networks
G Morohashi; S Iwata
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 329, 1-3, 237-250, Dec. 2004, Peer-reviwed, 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.
Scientific journal, English - 一般化ブロックパズルの PSPACE 完全性の別証明
北川智博; 岩田茂樹
京都大学数理解析研究所講究録, 1325, 209-214, May 2003
Research institution, Japanese - Some minimum merging networks
Gembu Morohashi; Shigeki Iwata
33rd Southeastern Conference on Combinatorics, Graph Theory, and Computing, 77, Mar. 2002, Peer-reviwed
International conference proceedings, English - Lower bounds for merging networks
S Iwata
INFORMATION AND COMPUTATION, ACADEMIC PRESS INC, 168, 2, 187-195, Aug. 2001, Peer-reviwed, 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.
Scientific journal, English - 一般化詰将棋問題の指数時間完全性
横田雅也; 築地立家; 北川智博; 諸橋玄武; 岩田茂樹
電子情報通信学会論文誌, J84-D-I, 3, 239-246, Mar. 2001, Peer-reviwed
Scientific journal, Japanese - 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, Peer-reviwed
Scientific journal, English - (4,7)-,(5,6)-マージングネットワークの最小比較器数のコンピュータによる計算
丹野岳久; 岩田茂樹
京都大学数理解析研究所講究録, 1054, 40-53, Jul. 1998
Research institution, Japanese - マージングネットワークの下界について
増田一寿; 岩田茂樹
電子情報通信学会論文誌, J80-D-I, 8, 665-673, Aug. 1997, Peer-reviwed
Scientific journal, Japanese - 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, Peer-reviwed
Scientific journal, English - 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, Peer-reviwed
Scientific journal, English - 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, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed
Research society, English - 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, Peer-reviwed, 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.
Scientific journal, English - Some EXPTIME complete problems on context-free languages
Takumi Tasai; Shigeki Iwata
IEICE Trans. Inf. & Syst., E76-D, 3, 329-335, Mar. 1993, Peer-reviwed
Scientific journal, English - Simulations of Turning machines by 2NPDA and their applications to open problems
Shigeki Iwata; Takumi Kasai
Congressus Numerantium, 72, 81-92, Feb. 1990, Peer-reviwed
Scientific journal, English - Generalized Hi-Q is NP-complete
Ryuhei Uehara; Shigeki Iwata
Trans. IEICE, 電子情報通信学会, E73, 2, 270-273, Feb. 1990, Peer-reviwed, 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.
Scientific journal, English - n×n盤面上の将棋の指数時間完全性について
安達博之; 亀川裕之; 岩田茂樹
電子情報通信学会論文誌, J70, 10, 1843-1852, Oct. 1987, Peer-reviwed
Scientific journal, Japanese - SIMULTANEOUS (POLY-TIME, LOG-SPACE) LOWER BOUNDS
S IWATA; T KASAI
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 54, 2-3, 325-329, 1987, Peer-reviwed
Scientific journal, English - Simple programs with a fixed number of variables seem still hard to analyze
Shigeki Iwata; Takumi Kasai
405-416, 1987, Peer-reviwed
English - 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, Peer-reviwed, 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.
Scientific journal, English - Gradually intractable problems and nondeterministic log-space
Takumi Kasai; Shigeki Iwata
Math. Systems Theory, 18, 153-170, 1985, Peer-reviwed
Scientific journal, English - Problem requiring k log n deterministic space
Shigeki Iwata; Takumi Kasai
Congressus Numerantium, 44, 161-174, Dec. 1984, Peer-reviwed
Scientific journal, English - 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, Peer-reviwed
Scientific journal, English - Graph theoretic problems complete for nondeterministic log-space
Yoshiaki Fukazawa; Shigeki Iwata
Trans. IECE, E66, 2, 102-107, Feb. 1983, Peer-reviwed
Scientific journal, English - Low level complexity for combinatirial games
Akeo Adachi; Shigeki Iwata; Takumi Kasai
Proc. 13rd Ann. ACM Symp. on Theory of Computing, 228-237, 1981, Peer-reviwed
International conference proceedings, English - Maximum number of prime implicants for a class of restricted boolean functions
Shigeki Iwata
Congressus Numerantium, 29, 531-534, Dec. 1980, Peer-reviwed
Scientific journal, English - Satisfiability problems require exponential time for monadic predicate caliculus
Shigeki Iwata; Takumi Kasai
Proc. Fifth IBM Symp. on Math. Found. of Comput. Sci., 1980, Peer-reviwed
International conference proceedings, English - Classes of pebble games and complete problems
Takumi Kasai; Akeo Adachi; Shigeki Iwata
SIAM J. Comput., 8, 4, 574-586, Nov. 1979, Peer-reviwed
Scientific journal, English - Programs with minimal number of goto statements
Shigeki Iwata
Information and Control, 37, 1, 105-114, Apr. 1978, Peer-reviwed
Scientific journal, English - Classes of pebble games and complete problems
Takumi Kasai; Akeo Adachi; Shigeki Iwata
Proc. 1978 Ann. Conf. ACM 78, 914-918, 1978, Peer-reviwed
International conference proceedings, English
Books and other publications
Lectures, oral presentations, etc.
- 上書きハッシュ表の性質
山口陽平; 岩田茂樹
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