岩本 宙造Chuzo Iwamoto

Last Updated :2025/04/03

所属・職名
大学院先進理工系科学研究科　教授
ホームページ
https://home.hiroshima-u.ac.jp/chuzo/
メールアドレス
chuzohiroshima-u.ac.jp
自己紹介
平成2年山口大学工学部電子工学科卒業．平成4年九州大学大学院工学研究科情報工学専攻修士課程修了．平成7年同大学大学院工学研究科情報工学専攻博士課程後期修了．博士（工学）．平成4年8月より1年間，学生国際交流制度による日本国政府文部省派遣留学生として，カナダのMcGill大学に在籍．平成4年から2年間，日本学術振興会特別研究員．平成7年4月九州大学工学部助手．平成7年11月九州芸術工科大学（現九州大学芸術工学部）専任講師．平成9年10月広島大学工学部助教授，准教授．平成26年広島大学大学院工学研究科情報工学専攻教授となり現在に至る．平成14年10月より1年間，文部科学省在外研究員として，フランスのUniversite de Metzに滞在．主として計算複雑性理論に関する研究に従事．

基本情報

主な職歴

  • 1993年04月01日, 1995年03月31日, 日本学術振興会, 特別研究員DC
  • 1995年04月01日, 1995年10月31日, 九州大学, 工学部, 助手
  • 1995年11月01日, 1997年09月30日, 九州芸術工科大学, 芸術工学部, 専任講師
  • 1997年10月01日, 2001年03月31日, 広島大学, 工学部, 助教授
  • 2001年04月01日, 2007年03月31日, 広島大学, 大学院工学研究科, 助教授
  • 2007年04月01日, 2014年08月31日, 広島大学, 大学院工学研究科, 准教授
  • 2014年09月01日, 2020年03月31日, 広島大学, 大学院工学研究科, 教授
  • 2020年04月01日, 広島大学, 大学院先進理工系科学研究科, 教授

学歴

  • 九州大学, 工学研究科, 情報工学専攻, 日本, 1990年04月, 1995年03月
  • 山口大学, 工学部, 電子工学科, 日本, 1986年04月, 1990年03月

学位

  • 博士（工学）　(九州大学)

教育担当

  • 【学士課程】 情報科学部 : 情報科学科 : 計算機科学プログラム
  • 【博士課程前期】 先進理工系科学研究科 : 先進理工系科学専攻 : 情報科学プログラム
  • 【博士課程後期】 先進理工系科学研究科 : 先進理工系科学専攻 : 情報科学プログラム

研究分野

  • 情報学 / 情報学基礎 / 情報学基礎理論

研究キーワード

  • 計算複雑性理論
  • 組合せ論的計算幾何学

所属学会

教育活動

授業担当

  1. 2025年, 教養教育, ３ターム, 線形代数学II[1工二]
  2. 2025年, 学部専門, ２ターム, 離散数学I
  3. 2025年, 学部専門, １ターム, オートマトンと言語理論
  4. 2025年, 学部専門, 集中, プロジェクト研究
  5. 2025年, 学部専門, 集中, 長期フィールドワークI
  6. 2025年, 学部専門, １ターム, 計算機科学セミナーI
  7. 2025年, 学部専門, ２ターム, 計算機科学セミナーII
  8. 2025年, 学部専門, セメスター（後期）, 卒業論文
  9. 2025年, 修士課程・博士課程前期, １ターム, 情報科学特別演習A
  10. 2025年, 修士課程・博士課程前期, ２ターム, 情報科学特別演習A
  11. 2025年, 修士課程・博士課程前期, ３ターム, 情報科学特別演習B
  12. 2025年, 修士課程・博士課程前期, ４ターム, 情報科学特別演習B
  13. 2025年, 修士課程・博士課程前期, 年度, 情報科学特別研究
  14. 2025年, 修士課程・博士課程前期, ３ターム, Computational Complexity Theory
  15. 2025年, 博士課程・博士課程後期, 年度, 情報科学特別研究

研究活動

学術論文（★は代表的な論文）

  1. Some Properties of Homogeneous Pyramid Automata, IEICE Transactions on Information and Systems (Japanese Edition), J73-D-I巻, 9号, pp. 778-780, 19900901
  2. RS-Vector Algorithms for Combinatorial Problems, IEICE Transactions on Information and Systems (Japanese Edition), J75-D-I巻, 3号, pp. 143-151, 19920301
  3. Parallelizabilities of Vertex Set Partition Problem, Proceedings of the Joint Symposium on Parallel Processing, 92巻, 1号, pp. 47-53, 19920601
  4. RS-Vector Algorithms for Combinational Problems, Systems and Computers in Japan, 24巻, 7号, pp. 41-51, 19930701
  5. Extended Graph Connectivity and Its Gradually Increasing Parallel Complexity, Proceedings of the fifth Annual International Symposium on Algorithms and Computation (Lecture Notes in Computer Science), 834巻, pp. 478-486, 19940801
  6. Finding Hamiltonian Circuits in Arrangements of Jordan Curves is NP-Complete, Proceedings of the Sixth Canadian Conference on Computational Geometry, pp. 93-98, 19940801
  7. Finding Hamiltonian circuits in arrangements of Jordan Curves Is NP-complete, Information Processing Letters, 52巻, pp. 183-189, 19941101
  8. On Problems with Gradually Increasing Parallel Complexities, Proceedings of the 1996 IEICE General Conference, pp. 361-362, 19960301
  9. A Faster Parallel Algorithm for k-Connectivity, Proceedings of the Second Korea-Japan Joint Workshop on Algorithms and Computation, pp. 8-13, 19960401
  10. Parallel Complexity Hierarchies Based on PRAMs and DLOGTIME-Uniform Circuits, Proceedings of the Eleventh Annual IEEE Conference on Computational Complexity, pp. 24-32, 19960501
  11. Alpha-Connectivity: A Gradually Nonparallel Graph Problem, Journal of Algorithms, 20巻, 3号, pp. 526-544, 19960501
  12. Time Lower Bounds Do Not Exist for CRCW PRAMs, Theoretical Computer Science, 155巻, pp. 411-424, 19960601
  13. How Can We Demonstrate Increasing Parallel Complexities?, ACM/UMIACS Fourth Workshop on Parallel Algorithms, 19970501
  14. Time Complexity Hierarchies of Extended TMs for Parallel Computation, IEICE Transactions on Information and Systems (Japanese Edition), J80-D-I巻, 5号, pp. 421-427, 19970501
  15. A Faster Parallel Algorithm for k-Connectivity, Information Processing Letters, 61巻, pp. 265-269, 19970601
  16. (1+o(1))S(n)-Space Is Stronger Than S(n)-Space, Proceedings of the 3rd JAPAN-KOREA Joint Workshop on Algorithms and Computation, pp. 72-79, 19970701
  17. A Canonical Form of Vector Machines, Information and Computation, 141巻, 1号, pp. 37-65, 19980401
  18. Complexity Hierarchies on DLOGTIME-Uniform Circuits and TMs with Restricted Symbols, Proceedings of the Eleventh Workshop on Circuits and Systems in Karuizawa, pp. 367-372, 19980401
  19. Improved Time and Space Hierarchies of One-Tape Off-Line TMs, Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science (Lecture Notes of Computer Science), 1450巻, pp. 580-588, 19980801
  20. Periodic Recession and R＆D Management in Japan, Proceedings of the IEEE EMS International Engineering Management Conference, pp. 198-201, 19990501
  21. Space Hierarchies of Turing Machines with Restricted Tape Symbols, IEICE Transactions on Information and Systems (Japanese Edition), J82-D-I巻, 6号, pp. 661-668, 19990601
  22. Technological Changes and the Effect of Business Cycles in Electric Manufacturing Companies for the Postwar 50 Years, Transactions of the Institute of Electrical Engineers of Japan (Japanese Edition), 119-A巻, 6号, pp. 725-730, 19990601
  23. Juglar Cycles and Their Effects on Technological Changes, Portland International Conference on Management of Engineering and Technology, Proceedings Vol-1: Book of Summaries, Proceedings Vol-2: Papers Presented at PICMET’99, 1,2巻, pp. 17-34, 19990701
  24. On Time-Constructible Functions in One-Dimensional Cellular Automata, Proceedings of the 12th International Symposium on Fundamentals of Computation Theory (Lecture Notes in Computer Science), 1684巻, pp. 316-326, 19990801
  25. Universality of the Language Generating Ability of Two-Point Splicing Systems, IEICE Transactions on Information and Systems (Japanese Edition), J83-DI巻, 1号, pp. 55-59, 20000101
  26. Application of Finite Difference Method to Arbitrary Mesh Points, Transactions of The Institute of Electrical Engineers of Japan (Japanese Edition), 120-A巻, 2号, pp. 116-121, 20000201
  27. Speeding-Up Cellular Automata by Alternations, Proceedings of Machines Computations and Universality (Lecture Notes in Computer Science), 2055巻, pp. 240-251, 20010501
  28. A three-dimensional uniquely parsable array grammar that generates and parses cubes, Electric Notes in Theoretical Comupter Science, 46巻, pp. 1-16, 20010801
  29. Constructible functions in cellular automata and their applications to hierarchy results, Theoretical Computer Science, 270巻, 1-2号, pp. 797-809, 20020106
  30. Computational Complexity in the Hyperbolic Plane, Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science (Lecture Notes in Computer Science), 2420巻, pp. 365-374, 20020801
  31. Embedding a logically universal model and a self-reproducing model into number-conserving cellular automata, Proceedings of the Third International Conference on Unconventional Models of Computation (UMC2002) Lecture Notes in Computer Science), 2509巻, pp. 164-175, 20021015
  32. A quadratic speedup theorem for iterative arrays, Acta Informatica, 38巻, 11-12号, pp. 847-858, 20021101
  33. Self-reproduction and shape formation in two and three dimensional cellular automata with conservative constraints, Proceedings of the Eighth International Symposium on Artificial Life and Robotics (AROB2003), pp. 377-380, 20030101
  34. Simulations between multi-dimensional deterministic and alternating cellular automata, Fundamenta Informaticae, 58巻, 3-4号, pp. 261-271, 20031201
  35. A logically universal number-conserving cellular automaton with a unary table-lookup function, IEICE Transactions on Information and Systems, E87D巻, 3号, pp. 694-699, 20040301
  36. Time and space complexity classes of hyperbolic cellular automata, IEICE Transactions on Information and Systems, E87D巻, 3号, pp. 700-707, 20040301
  37. Prefix computations on iterative arrays with sequential input/output mode, IEICE Transactions on Information and Systems, E87D巻, 3号, pp. 708-712, 20040301
  38. Partially effective randomization in simulations between ARBITRARY and COMMON PRAMs, Journal of Parallel and Distributed Computing, 64巻, 3号, pp. 319-326, 20040301
  39. Hierarchies of DLOGTIME-Uniform Circuits, M. Margenstern (ed.): Machines Computations and Universality (Proc. MCU 2004 Saint-Petersburg Russia September 21-26 2004) Lecture Notes in Computer Science, 3354巻, pp. 211-222, 20050201
  40. Translational lemmas for alternating TMs and PRAMs, Proceedings of the 15th International Symposium on Fundamentals of Computation Theory (Lecture Notes in Computer Science), 3623巻, pp. 137-148, 20050817
  41. A five-state von Neumann neighbor universal hyperbolic cellular automaton, Journal of Cellular Automata, 1巻, 4号, pp. 275-297, 20061201
  42. A Time Hierarchy Theorem for Nondeterministic Cellular Automata, Proceedings of the 4th Annual Conference on Theory and Applications of Models of Computation (Lecture Notes in Computer Science), 4484巻, pp. 511-520, 20070501
  43. Translational Lemmas for DLOGTIME-uniform Circuits, Alternating TMs, and PRAMs, Acta Informatica, 44巻, 5号, pp. 345-359, 20070501
  44. Special Section on Foundations of Computer Science, IEICE Transactions on Information and Systems, E91-D巻, 2号, pp. 161-161, 20080201
  45. A Java Based Three-Dimensional Cellular Automata Simulator and its Application to Three-Dimensional Larger Than Life, Proceedings of Automata 2008: Theory and Applications of Cellular Automata, Bristol, UK, Luniver Press, pp. 413-416, 20080601
  46. A recursive padding technique on nondeterministic cellular automata, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E91A巻, 9号, pp. 2335-2340, 20080901
  47. On the non-existence of rotation-symmetric von Neumann neighbor number-conserving cellular automata of which the state number is less than four, IEICE Transactions on Information and Systems, E92-D巻, 2号, pp. 255-257, 20090201
  48. An Efficient Reconstruction Algorithm for Restricted Domino Tilings, IEICE Transactions on Information and Systems (Japanese Edition), J92-D巻, 6号, pp. 758-766, 20090601
  49. Computational Complexity of Cast Puzzles, Proceedings of the 20th International Symposium on Algorithms and Computation (Lecture Notes in Computer Science), 5878巻, pp. 122-131, 20091201
  50. On designing gliders in three-dimensional Larger Than Life cellular automata, F. Peper et al. (eds.): Natural Computing (Proceedings in Information and Communications Technology), 2巻, pp. 184-190, 20100201
  51. A Tight Space-Hierarchy Theorem for Nondeterministic Turing Machines, IEICE Transactions on Information and Systems (Japanese Edition), J93-D巻, 9号, pp. 1717-1726, 20100901
  52. NP-Hard and k-EXPSPACE-Hard Cast Puzzles, IEICE Transactions on Information and Systems, E93D巻, 11号, pp. 2995-3004, 20101101
    DOIを用いた論文検索結果へのリンク
  53. Relationship between Depth and Nondeterministic Gates in Nondeterministic Circuit Families, IPSJ Journal (Japanese Edition), 5巻, 4号, pp. 1667-1677, 20110401
  54. Computational Complexity of String Puzzles, Proceedings of the 18th Computing: the Australasian Theory Symposium (CRPIT, 128, Mestre, J. Eds., ACS.), 128巻, pp. 69-74, 20120101
  55. Lower Bound of Face Guards of Polyhedral Terrains, Journal of Information Processing, 20巻, 2号, pp. 435-437, 20120401
  56. A Polynomial-Time Reduction from the 3SAT Problem to the Generalized String Puzzle Problem", Algorithms, 5巻, 2号, pp. 261-272, 20120401
  57. Improved Lower and Upper Bounds of Face Guards of Polyhedral Terrains, Transactions on Information and Systems (Japanese Edition), J95-D巻, 10号, pp. 1869-1872, 20121001
  58. Generalized Shisen-Sho is NP-Complete, IEICE Transactions on Information and Systems, E95D巻, 11号, pp. 2712-2715, 20121101
    DOIを用いた論文検索結果へのリンク
  59. Finding the Minimum Number of Face Guards is NP-Hard, IEICE Transactions on Information and Systems, E95D巻, 11号, pp. 2716-2719, 20121101
    DOIを用いた論文検索結果へのリンク
  60. Generalized Chat Noir is PSPACE-Complete, IEICE Transactions on Information and Systems, E96D巻, 3号, pp. 502-505, 20130301
    DOIを用いた論文検索結果へのリンク
  61. Locating the Minimum Number of Guards with r-visibility in a Polyomino is NP-hard, The 16th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2013), pp. 100-101, 20130901
  62. Generalized Pyramid is NP-Complete, IEICE Transactions on Information and Systems, E96D巻, 11号, pp. 2462-2465, 20131101
    DOIを用いた論文検索結果へのリンク
  63. Universal von Neumann Neighborhood Cellular Automata on Penrose Tilings, Proceedings of the 1st International Workshop on Applications and Fundamentals of Cellular Automata, pp. 515-521, 20131201
  64. Yosenabe is NP-complete, Journal of Information Processing, 22巻, 1号, pp. 40-43, 20140101
  65. Computational Complexity of the r-visibility Guard Set Problem for Polyominoes, Lecture Notes in Computer Science, Springer-Verlag, 8845巻, pp. 87-95, 20141101
  66. Computational Complexity of Generalized Forty Thieves, IEICE Transactions on Information and Systems, E98D巻, 2号, pp. 429-432, 20150201
    DOIを用いた論文検索結果へのリンク
  67. Computational Complexity of Generalized Golf Solitaire, IEICE Transactions on Information and Systems, E98D巻, 3号, pp. 541-544, 20150301
    DOIを用いた論文検索結果へのリンク
  68. Visibility Problems for Manhattan Towers, IEICE Transactions on Information and Systems, E99-D巻, 3号, pp. 607-614, 20160301
  69. Computational Complexity of Building Puzzles, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E99-A巻, 6号, pp. 1145-1148, 20160601
  70. Finding the Minimum Number of Open-Edge Guards in an Orthogonal Polygon is NP-hard, IEICE Transactions on Information and Systems, E100-D巻, 7号, pp. 1521-1525, 20170701
  71. NP-completeness of Mojipittan, IEICE Transactions on Information and Systems (Japanese Edition), J100-D巻, 12号, pp. 974-977, 20171201
  72. Dosun-Fuwari is NP-complete, Journal of Information Processing, 26巻, pp. 358-361, 20180401
  73. Herugolf and Makaro are NP-complete, Proceedings of the Ninth International Conference on Fun with Algorithms (FUN 2018), 100巻, 24号, pp. 24:1-24:11, 20180613
  74. Computational Complexity of Usowan Puzzles, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E101-A巻, 9号, pp. 1537-1540, 20180901
  75. Kurotto and Juosan are NP-complete, The 21st Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2018), pp. 46-48, 20180901
  76. Nurimisaki and Sashigane are NP-complete, The 31st Canadian Conference on Computational Geometry (CCCG 2019), pp. 184-194, 20190801
  77. Computational Complexity of Herugolf and Makaro, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E102-A巻, 9号, pp. 1118-1125, 20190901
  78. Polynomial-Time Reductions from 3SAT to Kurotto and Juosan Puzzles, IEICE Transactions on Information and Systems, E103-D巻, 3号, pp. 500-505, 20200301
    DOIを用いた論文検索結果へのリンク
  79. Computational Complexity of the Chromatic Art Gallery Problem for Orthogonal Polygons, The 14th International Conference and Workshop on Algorithms and Computation (R.M. Sohel et al.(Eds): WALCOM 2020, Lecture Notes in Computer Science), 12049巻, pp. 146-157, 20200401
    DOIを用いた論文検索結果へのリンク
  80. Computational Complexity of Nurimisaki and Sashigane, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E103-A巻, 10号, pp. 1183-1192, 20201001
    DOIを用いた論文検索結果へのリンク
  81. Chromatic Art Gallery Problem with r-visibility is NP-complete, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E104-A巻, 9号, pp. 1108-1115, 20210901
  82. Computational Complexity of Two Pencil Puzzles: Kurotto and Juosan, Lecture Notes in Computer Science, Springer-Verlag, 13034巻, pp. 175-185, 20211101
  83. Five Cells and Tilepaint are NP-complete, IEICE Transactions on Information and Systems, E105-D巻, 3号, pp. 508-516, 20220301
  84. Vertex-to-Point Conflict-Free Chromatic Guarding is NP-hard, Lecture Notes in Computer Science, Springer-Verlag, 13174巻, pp. 111-122, 20220324
  85. Moon-or-Sun, Nagareru, and Nurimeizu are NP-complete, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E105-A巻, 9号, pp. 1187-1194, 20220901
  86. Calculation Solitaire is NP-complete, IEICE Transactions on Information and Systems, E106-D巻, 3号, pp. 328-332, 20230301
  87. Computational Complexity of Sukoro, IEICE Transactions on Information and Systems, J106-D巻, 5号, pp. 357-361, 20230501
  88. Yajisan-Kazusan and Stained Glass are NP-complete, The 23rd Japan-Korea Joint Workshop on Algorithms and Computation, pp. 227-233, 20230624
  89. Computational Complexity of the Vertex-to-Point Conflict-Free Chromatic Art Gallery Problem, IEICE Transactions on Information and Systems, E106-D巻, 9号, pp. 1499-1506, 20230901
  90. Chained Block is NP-complete, IEICE Transactions on Information and Systems, E107-D巻, 3号, pp. 320-324, 20240301
  91. Choco Banana is NP-complete, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E107-A巻, 9号, pp. 1488-1491, 20240901
  92. The Chromatic Dispersive Art Gallery Problem, The 26th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG3), pp. 120-121, 20240910
  93. Computational Complexity of Yajisan-Kazusan and Stained Glass, IEICE Transactions on Information and Systems, E108-D巻, 3号, pp. 201-207, 20250301
  94. Shinkamino is NP-complete, IEICE Transactions on Information and Systems (Japanese Edition), J108-D巻, 4号, pp. 199-203, 20250401
  95. Card-Based Zero-Knowledge Proof for Dosun-Fuwari, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E108-A巻, 9号, pp. 1-5, 20250901

著書等出版物

  1. 2003年11月, 量子コンピューティング , 森北出版, 2003年, 11, 単行本（学術書）, 共訳, jozef gruska 今井克暢 伊藤正美 外山政文 岩本宙造 森田憲一, 9784627827912, 491
  2. 2010年02月, 『階層定理』電子情報通信学会，知識ベース６群２編「計算論とオートマトン」，５章「決定性，非決定性計算の複雑さ」，第２節「階層定理」, 社団法人　電子情報通信学会, 2010年, 02, 事典・辞書, 共編著, 3
  3. 2016年12月09日, 専門基礎 微分積分学, 培風館, 2016年, 12, 単行本（学術書）, 共著, 日本語, 阿部誠，岩本宙造，島唯史，向谷博明, 978-4-563-01207-6, 231

招待講演、口頭・ポスター発表等

  1. How Can We Demonstrate Increasing Parallel Complexities?, Chuzo Iwamoto, ACM/UMIACS Fourth Workshop on Parallel Algorithms (WOPA1996), 1996年05月, 招待, 英語, ACM/UMIACS, Philadelphia, USA
  2. 対数時間一様回路族および記号数限定TMの計算量の階層, 岩本 宙造, 第11回 回路とシステム（軽井沢）ワークショップ, 1998年04月, 招待, 日本語, 長野
  3. Complexity Hierarchies on Turing Machines, Uniform Circuits, and Cellular Automata, Chuzo Iwamoto, Abstracts of Invited Lectures and Short Communications Delivered at the Ninth CNACSA, 2000年08月, 招待, 英語, Bulgaria

受賞

  1. 1993年03月, 財団法人 電気通信普及財団 第２回 テレコム・コロンブス賞, Telecommunications Advancement Foundation, 組合せ問題に対するＲＳ型ベクトルアルゴリズム
  2. 2008年01月, 2007年度 LA/EATCS発表論文賞, LA Symposium, EATCS Japan Chapter, 段数５の単色ドミノタイリングの直交射影からの再構成
  3. 2009年11月26日, 情報・システムソサイエティ活動功労賞, （社）電子情報通信学会, 英文論文誌編集委員としての貢献
  4. 2011年06月, 情報・システムソサイエティ査読功労賞, （社）電子情報通信学会, 論文誌査読委員としての貢献
  5. 2018年02月06日, 2017年度 LA/EATCS発表論文賞, LA Symposium, EATCS Japan Chapter, ヘルゴルフのＮＰ完全性