岩田　茂樹

名誉教授・その他関係者名誉教授
研究者情報

学位

  • 工学博士, 早稲田大学

研究キーワード

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

研究分野

  • 情報通信, 情報学基礎論

学歴

  • 1980年02月
    早稲田大学, 理工学研究科, 電気工学専攻
  • 1973年03月
    早稲田大学, 理工学研究科, 電気工学専攻
  • 1971年03月
    早稲田大学, 理工学部, 電気工学科

委員歴

  • 2006年05月 - 2012年05月
    編集顧問, 電子情報通信学会, 学協会
  • 2007年05月 - 2009年05月
    情報システムソサイエテイ副会長(編集担当）, 電子情報通信学会, 学協会
  • 2004年05月 - 2006年05月
    情報システムソサイエティ和文論文誌編集委員会委員長, 電子情報通信学会, 学協会
  • 2003年05月 - 2004年05月
    情報システムソサイエティ和文論文誌編集委員会副委員長, 電子情報通信学会, 学協会
  • 2000年05月 - 2004年05月
    情報システムソサイエティ和文論文誌編集委員, 電子情報通信学会, 学協会
  • 2002年05月 - 2003年05月
    情報システムソサイエティ和文論文誌編集委員会幹事, 電子情報通信学会, 学協会
研究活動情報

受賞

  • 受賞日 2009年07月
    電子情報通信学会
    電子情報通信学会フェロー

論文

  • 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, 88巻, 掲載ページ 237-246, 出版日 2012年07月, 査読付
    研究論文（学術雑誌）, 英語
  • Posets with seven linear extensions sortable by three comparisons
    Satoshi Hanamura; Shigeki Iwata
    INFORMATION PROCESSING LETTERS, 111巻, 8号, 掲載ページ 365-369, 出版日 2011年03月, 査読付
    研究論文（学術雑誌）, 英語
    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, 出版日 2010年07月, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • STONEHENGE: OUTCOME OF ALL FIRST MOVES AND PSPACE-COMPLETENESS
    Yasuhiko Takenaga; Hikari Mori; Shigeki Iwata
    ICGA JOURNAL, 33巻, 1号, 掲載ページ 34-41, 出版日 2010年03月, 査読付
    研究論文（学術雑誌）, 英語
  • 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, 出版日 2005年11月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • Some minimum merging networks
    G Morohashi; S Iwata
    THEORETICAL COMPUTER SCIENCE, 329巻, 1-3号, 掲載ページ 237-250, 出版日 2004年12月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 一般化ブロックパズルの 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, 168巻, 2号, 掲載ページ 187-195, 出版日 2001年08月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 一般化詰将棋問題の指数時間完全性
    横田雅也; 築地立家; 北川智博; 諸橋玄武; 岩田茂樹
    電子情報通信学会論文誌, 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, 123巻, 2号, 掲載ページ 329-340, 出版日 1994年01月, 査読付
    研究論文（学術雑誌）, 英語
    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年, 査読付
    研究論文（その他学術会議資料等）, 英語
  • RELATIONS AMONG SIMULTANEOUS COMPLEXITY CLASSES OF NONDETERMINISTIC AND ALTERNATING TURING-MACHINES
    S IWATA; T KASAI; E MORIYA
    ACTA INFORMATICA, 30巻, 3号, 掲載ページ 267-278, 出版日 1993年05月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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.
    研究論文（学術雑誌）, 英語
    URL
  • n×n盤面上の将棋の指数時間完全性について
    安達博之; 亀川裕之; 岩田茂樹
    電子情報通信学会論文誌, J70巻, 10号, 掲載ページ 1843-1852, 出版日 1987年10月, 査読付
    研究論文（学術雑誌）, 日本語
  • SIMULTANEOUS (POLY-TIME, LOG-SPACE) LOWER BOUNDS
    S IWATA; T KASAI
    THEORETICAL COMPUTER SCIENCE, 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年, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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., 31巻, 2号, 掲載ページ 361-376, 出版日 1984年, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • Programs with minimal number of goto statements
    Shigeki Iwata
    Information and Control, 37巻, 1号, 掲載ページ 105-114, 出版日 1978年04月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • Classes of pebble games and complete problems
    Takumi Kasai; Akeo Adachi; Shigeki Iwata
    Proc. 1978 Ann. Conf. ACM 78, 掲載ページ 914-918, 出版日 1978年, 査読付
    研究論文（国際会議プロシーディングス）, 英語

書籍等出版物

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

講演・口頭発表等

  • 上書きハッシュ表の性質
    山口陽平; 岩田茂樹
    口頭発表（一般）, 日本語, 第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月

所属学協会

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