論文の概要: Iterated Narrow Networks: Turing Completeness at Width 4 on Convex Input Spaces and the Complexity of Verification

• arxiv url: http://arxiv.org/abs/2611.02840v1
• Date: Mon, 02 Nov 2026 09:41:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-06 14:56:58.48596
• Title: Iterated Narrow Networks: Turing Completeness at Width 4 on Convex Input Spaces and the Complexity of Verification
• Title（参考訳）: 繰り返しナローネットワーク:凸入力空間の幅4でのチューリング完全性と検証の複雑さ
• Abstract要約: 固定 ReLU ネットワーク $N$ of width 4, すなわち離散時間系 $x_k+1 = N(x_k)$ on $[0,1]4$ の反復について検討する。 すべてのチューリングマシンがそのようなネットワークを$N_M$で認めることを証明している。 繰り返し幅4のReLUネットワークの到達性は、時間境界の単一軸に沿った完全な階層にまたがる。
• 参考スコア（独自算出の注目度）: 1.5850545634216486
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the iterates of a fixed ReLU network $N$ of width 4, that is, the discrete-time system $x_{k+1} = N(x_k)$ on $[0,1]^4$. Equivalently, $x_k$ is the output of a weight-tied network made of $k$ copies of $N$, or of a recurrent network with no external input, started at $x_0$. We prove that every deterministic Turing machine $M$ admits such a network $N_M$. The network can be constructed in polynomial time from $M$. Each iteration has depth $\mathrm{poly}(|M|)$. The iterates of $N_M$ simulate $M$ exactly on every encoded tape. The number of iterations is proportional to the running time of $M$. Moreover, the fourth coordinate irreversibly flags every point of the convex cube $[0,1]^4$ whose simulation reads an invalid digit. This flag is the certificate that makes hardness reductions sound on convex input regions, the regime of practical verifiers. Convex regions were previously inaccessible because of a continuity obstruction inherent to ReLU networks. The correspondence has three consequences. First, reachability for iterated width-4 ReLU networks spans the full complexity hierarchy along the single axis of the time bound: it is NP-complete for a unary bound, NEXP-complete for a binary bound and RE-complete (undecidable) with no bound. Second, two extra neurons of width suffice to extend the hardness to every common smooth activation: at width 6, the robust verification problem (a promise problem with $δ/2δ$ gap) is NP-complete for $\tanh$, sigmoid, GELU, Swish, ELU, and any polynomial-time-computable continuous non-polynomial activation with a polynomial-time-computable Lipschitz constant. Third, the whole spectrum transfers to discretized Neural ODEs in dimension 5.
• Abstract（参考訳）: 固定 ReLU ネットワーク $N$ of width 4, すなわち離散時間系 $x_{k+1} = N(x_k)$ on $[0,1]^4$ の反復について検討する。 同様に$x_k$は$N$の$k$コピーからなる重み付けネットワークの出力であり、外部入力のない再帰ネットワークは$x_0$から始まる。 我々は、すべての決定論的チューリングマシン$M$がそのようなネットワーク$N_M$を認めることを証明している。 ネットワークは多項式時間で$M$から構築できる。 各反復は深さ$\mathrm{poly}(|M|)$である。 N_M$の繰り返しは、エンコードされたすべてのテープに正確に$M$をシミュレートする。 反復回数は、M$のランニング時間に比例する。 さらに、第4座標は、そのシミュレーションが無効な桁を読み取る凸立方体$[0,1]^4$のすべての点を不可逆的にフラグする。 このフラグは、実用的な検証の体制である凸入力領域の硬さを下げる証明書である。 凸領域は、ReLUネットワーク固有の連続性障害のため、以前はアクセス不能であった。 その対応には3つの結果がある。 第一に、繰り返し幅4のReLUネットワークへの到達性は、時間境界の単一軸に沿った完全な複雑性階層にまたがる: NP-完全は単項境界に対して、NEXP-完全は二項境界に対して、再完備(決定不能)は無境界である。 第二に、幅6において堅牢な検証問題(δ/2δ$ギャップを持つ約束問題)は、$\tanh$, sigmoid, GELU, Swish, ELUのNP完全であり、多項式時間計算可能なリプシッツ定数を持つ任意の多項式時間計算可能な連続非多項式活性化である。 第3に、全スペクトルは次元5の離散化ニューラルODEに転送される。

関連論文リスト

• Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization [59.290497104061835]
  私たちは$n$ノードのネットワーク上に$()$-Goldsteinの固定子を見つけます。 $d$への依存は、高次元のレジームにおいて大きなボトルネックとなる。 対数$d$への依存は、追加の通信だけで取り除くことができることを示す。
  論文  参考訳（メタデータ） (2026-10-05T04:37:04Z)
• A law of robustness for two-layer neural networks with arbitrary weights [0.0]
  Bubeck、Li、Nagarajは、一般的なデータでは、ノイズラベルに適合する$m$のニューロンを持つ任意の2層ニューラルネットワークは、リプシッツ定数を持つ必要があると推測した。 予想法則を1つの対数係数まで証明し、特にReLUネットワークにおいて連続的な片方向線形活性化を行う。
  論文  参考訳（メタデータ） (2026-07-08T17:44:15Z)
• Constructive Universal Approximation and Finite Sample Memorization by Narrow Deep ReLU Networks [0.0]
  我々は$N$の異なる点を持つデータセットが$mathbbRd$と$M$の出力クラスを正確に分類できることを示した。 また、任意の有界領域に対して$Lp(Omega; mathbbRm)$の普遍近似定理も証明する。 我々の結果は、深層ニューラルネットワークにおける制御性、表現性、およびトレーニングのダイナミクスを接続する統一的で解釈可能なフレームワークを提供する。
  論文  参考訳（メタデータ） (2024-09-10T14:31:21Z)
• Most Neural Networks Are Almost Learnable [52.40331776572531]
  固定された$epsilon>0$とdeep $i$に対して、深さ$i$のランダムなXavierネットワークを学習するポリ時間アルゴリズムが存在することを示す。 このアルゴリズムは時間とサンプルの複雑さが$(bard)mathrmpoly(epsilon-1)$であり、$bar d$はネットワークのサイズである。 シグモイドやReLU様の活性化の場合、境界は$(bard)mathrmpolylog(eps)に改善できる。
  論文  参考訳（メタデータ） (2023-05-25T22:27:42Z)
• Shallow neural network representation of polynomials [91.3755431537592]
  d+1+sum_r=2Rbinomr+d-1d-1[binomr+d-1d-1d-1[binomr+d-1d-1d-1]binomr+d-1d-1d-1[binomr+d-1d-1d-1]binomr+d-1d-1d-1]
  論文  参考訳（メタデータ） (2022-08-17T08:14:52Z)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。 テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。 さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
  論文  参考訳（メタデータ） (2022-07-15T11:55:09Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。