| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2026-10-26 15:25 一様な算術回路族が定義する代数的計算量クラスの非決定性および交代性半環チューリング機械による特徴づけ ○有村博紀（北大）  COMP2026-16 |
|
| 抄録 | （和） | 本稿では，人工知能分野における代数的モデル計数問題の計算量を特徴付けるために，最近 Badia, Droste, Eiter, Kiesel, Noguera, and Paulら (arXiv 2025)によって提案された環$mathbb F$上の重み付き非決定性チューリング機械（semiring Turing machines, またはweighted nondeterministic Turing machine, W-NTM）と呼ばれる重み付き計算機械の一種と，それを拡張した重み付き交代性機械(W-ATM)の計算能力を考察する．このW-NTMとW-ATMは，遷移関係に固定された遷移重みに加え，入力テープから読み込んだ$mathbb F$の元を用いて状態遷移を行うことができ，従来の伝統的な重み付き機械が有限生成環しか扱えないのに対して，無限生成環上の多項式を計算可能である．本稿では，この重み付き計算機械を，Valiant (STOC 1979)による代数的計算量理論における一様機械と位置付け，算術回路の一様族と能力を比較する． 主結果として，古典的計算の多項式時間計算可能問題の族cls{P}に対応する代数的計算問題の族$idsf{VP}$の一様版$cls{Unif VP}$と，その内側の一様族$cls{Unif VF}$, $cls{Unif VBP}$に対して，非決定性と交代性の重み付きチューリング機械による特徴付けを示す．この結果は，代数的計算において，サイズ・深さ・次数が限定された算術回路と，領域・時間・証明木サイズが有界な計算機械の非決定性および交代性計算との厳密な対応関係を示す初めての結果であり，古典的ブール計算における1980から1990年代にRuzzo(JCSS 1981)とVenkateswaran(SICOMP 1992)によって示されたブール回路と計算機械の間の特徴づけの代数的計算における対応物を与える．さらに，人工知能分野で最近研究が盛んな一般化計数問題と代数的計算量理論をつなぐものである． |
| （英） | This paper considers the power of nondeterministic and alternating semiring Turing machines (SRTMs), recently proposed by Badia, Droste, Eiter, Kiesel, Noguera, and Paul (arXiv 2025), referred to as weighted Turing machines (W-NTM and W-ATM) in this paper. As a generalization of weighted Turing machines, SRTMs can make transitions using not only hardwired weights but also arbitrary ring elements read from the input tape.Under a very restricted notion of uniformity, we establish the first machine-based characterizations for the uniform versions of Valiant's algebraic complexity classes VP, an algebraic complexity theoretic counterpart of the class NP of nondeterministic polynomial time, and classes VF and VBP inside VP. In algebraic complexity, these results demonstrate at the first time interesting correspondences between circuits with bounded size, depth, and degree, and nondeterministic and alternating computation of SRTMs with bounded space, time, and proof tree size. Furthermore, these results connect algebraic complexity theory with recent advances in generalized counting problems in artificial intelligence. | |
| キーワード | （和） | Valiantの代数的計算量理論 / 一様算術回路族 / 重み付きチューリング機械 / 非決定性・交代性チューリング機械 / 一般化計数問題 / / / |
| （英） | Valiant's framework for algebraic complexity theory / uniform arithmetic circuits / weighted Turing machines / nondeterministic and alternating computation / generalized counting problems / / / | |
| 文献情報 | 信学技報, vol. 126, no. 210, COMP2026-16, pp. 43-50, 2026年10月. | |
| 資料番号 | COMP2026-16 | |
| 発行日 | 2026-10-19 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2026-16 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2026-10-26 - 2026-10-26 |
| 開催地（和） | 東北大学 川内キャンパス マルチメディア教育研究棟 M601大ホール |
| 開催地（英） | 東北大学 川内キャンパス マルチメディア教育研究棟 M601大ホール |
| テーマ（和） | 理論計算機科学，一般 |
| テーマ（英） | Theoretical Computer Science, etc |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2026-10-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | 一様な算術回路族が定義する代数的計算量クラスの非決定性および交代性半環チューリング機械による特徴づけ |
| サブタイトル（和） | |
| タイトル（英） | Characterizing Algebraic Complexity Classes Defined by Uniform Arithmetic Circuit Families via Nondeterministic and Alternating Semiring Turing Machines |
| サブタイトル（英） | |
| キーワード(1)（和/英） | Valiantの代数的計算量理論 / Valiant's framework for algebraic complexity theory |
| キーワード(2)（和/英） | 一様算術回路族 / uniform arithmetic circuits |
| キーワード(3)（和/英） | 重み付きチューリング機械 / weighted Turing machines |
| キーワード(4)（和/英） | 非決定性・交代性チューリング機械 / nondeterministic and alternating computation |
| キーワード(5)（和/英） | 一般化計数問題 / generalized counting problems |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 有村 博紀 / Hiroki Arimura / アリムラ ヒロキ |
| 第1著者 所属（和/英） | 北海道大学 (略称： 北大) Hokkaido University (略称： Hokkaido Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2026-10-26 15:25:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2026-16 |
| 巻番号（vol） | vol.126 |
| 号番号（no） | no.210 |
| ページ範囲 | pp.43-50 |
| ページ数 | 8 |
| 発行日 | 2026-10-19 (COMP) |
[研究会発表申込システムのトップページに戻る] (日本語ページの行間係数: 1)