IWATA SHIGEKI

Emeritus Professor etc.Emeritus Professor
Researcher Information

Degree

  • Doctor of Engineering, Waseda University

Research Keyword

  • combinatorial theory
  • complexity
  • algorithm
  • 組合せ理論
  • 計算量
  • アルゴリズム

Field Of Study

  • Informatics, Information theory

Educational Background

  • 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, 電気工学科

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

Award

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

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, 88, 237-246, Jul. 2012, Peer-reviwed
    Scientific journal, English
  • Posets with seven linear extensions sortable by three comparisons
    Satoshi Hanamura; Shigeki Iwata
    INFORMATION PROCESSING LETTERS, 111, 8, 365-369, Mar. 2011, Peer-reviwed
    Scientific journal, English
    DOI URL
  • 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, 33, 1, 34-41, Mar. 2010, Peer-reviwed
    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, E88A, 11, 3264-3266, Nov. 2005, Peer-reviwed
    Scientific journal, English
    DOI URL
  • Some minimum merging networks
    G Morohashi; S Iwata
    THEORETICAL COMPUTER SCIENCE, 329, 1-3, 237-250, Dec. 2004, Peer-reviwed
    Scientific journal, English
    DOI URL
  • 一般化ブロックパズルの 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, 168, 2, 187-195, Aug. 2001, Peer-reviwed
    Scientific journal, English
    DOI URL
  • 一般化詰将棋問題の指数時間完全性
    横田雅也; 築地立家; 北川智博; 諸橋玄武; 岩田茂樹
    電子情報通信学会論文誌, 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, 123, 2, 329-340, Jan. 1994, Peer-reviwed
    Scientific journal, English
    DOI URL
  • 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, 30, 3, 267-278, May 1993, Peer-reviwed
    Scientific journal, English
    DOI URL
  • 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
    URL
  • 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, 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
    Scientific journal, English
    DOI URL
  • 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, 31, 2, 361-376, 1984, Peer-reviwed
    Scientific journal, English
    DOI URL
  • 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
    DOI URL
  • Programs with minimal number of goto statements
    Shigeki Iwata
    Information and Control, 37, 1, 105-114, Apr. 1978, Peer-reviwed
    Scientific journal, English
    DOI URL
  • 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

  • NP完全問題入門
    岩田茂樹
    Japanese, 共立出版, May 1995
  • 有限オートマトン入門
    岩田茂樹; 笠井琢美
    Japanese, 森北出版, May 1986

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

Affiliated academic society

  • ACM(Association for Computing Machinery)
  • EATCS(European Association for Theoretical Computer Science)
  • 電子情報通信学会