論文の概要: Syntactic Separation Implies Computational Indistinguishability: An Abstract Obstruction Theorem
- arxiv url: http://arxiv.org/abs/2606.29177v1
- Date: Sun, 28 Jun 2026 03:46:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-30 18:07:15.82409
- Title: Syntactic Separation Implies Computational Indistinguishability: An Abstract Obstruction Theorem
- Title（参考訳）: 統語的分離は計算的不明瞭性に影響を及ぼす:抽象的閉塞理論
- Abstract要約: 局所構文系 R はモデルに言及することなく半径 r0 の範囲内で作用する。
2つのスコレム函数が R で構文的に分離されているとき、導出はそれらの同値性を証明することができない。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We prove that syntactic separation implies computational indistinguishability. A local syntactic system R acts on terms within radius r0 without consulting any model; when two Skolem functions are syntactically separated in R, no derivation can prove their equivalence (Case 1), and any sound local extension requires Omega(n) steps, improving to Omega(2^n) under clause-per-configuration encoding (Case 2). Both bounds are new: the derivation-length lower bound does not appear in prior work on Skolemization or saturation proving, and the cryptographic reading, syntactic separation as ciphertext indistinguishability, derivation cost as negligible advantage, is original. The same obstruction, as formal instances of Case 1 and Case 2, governs the Natural Proofs barrier of Razborov and Rudich, the Type Omitting Theorem, and the unconditional AC^0 barrier of Loff et al. (2026).
- Abstract（参考訳）: 統語的分離は、計算上の不明瞭さを意味することを証明している。
局所構文系 R は半径 r0 内の項でモデルに言及することなく作用し、2つのスコレム函数が R でシンタクティックに分離されたとき、導出はそれらの同値性を証明することができず(Case 1)、任意の局所拡張は Omega(n) ステップを必要とし、節ごとの符号化(Case2)の下では Omega(2^n) に改善される。
両方の境界は新しいもので、導出長の低い境界は、スコレマイゼーションや飽和証明の先行研究には現れず、暗号読出、構文的分離、暗号文の区別不可能性、導出コストは無視可能な優位性である。
ケース1とケース2の正式な例と同様の障害は、ラズボロフとルディッチの自然証明障壁、オミッティング理論のタイプ、およびLoff et al (2026)の無条件AC^0障壁を支配している。
関連論文リスト
- Comments on the recent improvements of the MRRW bounds [59.04174294928297]
本稿では,コードワードに付随する単一ベクトルを部分空間に置き換えるスペクトル法の拡張として,OpenAI証明を符号化理論の言語と文脈に提示する。
また、符号化理論の言語と文脈におけるOpenAI証明を、コードワードに付随する1つのベクトルを部分空間に置き換えるスペクトル法の拡張として提示する。
論文 参考訳（メタデータ） (2026-09-01T20:43:23Z) - An Exactness Barrier for ZX-Calculus Optimization of Synthesized Clifford+T Circuits [3.825239835665478]
ゲートと回路の最適化は通常別々に研究される。
両方の動作がひとつのバウンドから続くことを示す。
これは、ニアヌル最適化パイプラインのサイズを説明し、予測する。
論文 参考訳（メタデータ） (2026-08-24T04:53:20Z) - What Syntax Cannot See: The Dynamic Syntactic Invariance Principle and Several Instances of the Same Hidden Assumption, and a Contradiction [0.0]
本稿では, 一つの手法を開発し, 受理結果を無声で仮定し, 変数とし, 一度落として何に従うかを証明する。
共通点のないドメイン間で動作し続けることを示すものだ。
論文 参考訳（メタデータ） (2026-08-02T03:10:44Z) - AI-Assisted Discovery of Convex Relaxations via Dual Agents [56.60366723277675]
すべての許容関数に対して下界が成り立ち、より強い境界を与える凸緩和から従うことを示す。
理論は各エージェントを検証し、反例を検索し、報告されたすべての境界はインターバルにおける明示的な二重実現可能な点によって認証される。
論文 参考訳（メタデータ） (2026-06-30T06:10:25Z) - C$^{2}$R: Cross-sample Consistency Regularization Mitigates Feature Splitting and Absorption in Sparse Autoencoders [56.67585330425431]
スパースオートエンコーダ(SAE)は、アクティベーションをスパースで人間の理解可能な機能に分解することで、大きな言語モデルを解釈するために広く使われている。
これらの問題は、サンプル間の一貫性のない潜在的な割り当てに起因している。
我々はC$2$Rを導入し、これは方向的に類似した潜伏剤の共活性化を罰する。
論文 参考訳（メタデータ） (2026-06-29T17:45:31Z) - A Measure-Theoretic Analysis of Reasoning: Structural Generalization and Approximation Limits [17.425526755350948]
離散軌跡を計量空間に投影し、領域シフトを定量化する。
カントロビッチ双対性を呼び起こすと、アーキテクチャ上のリプシッツ連続性と汎関数近似極限によるOOD一般化が成立する。
論文 参考訳（メタデータ） (2026-05-19T15:00:51Z) - Fault-Tolerant Resource Comparison of Qudit and Qubit Encodings for Diagonal Quadratic Operators [36.94429692322632]
有限局所ヒルベルト空間のトランケーションは、格子場の理論の量子シミュレーションにおいて自然に現れ、キュディエンコーディングを動機付ける。
実スカラー場の一様体-振幅の離散化において、実スカラー場を1つの論理的$d$-level qudit または$n_b=eil log drceil$ logical qubitsを用いて、$U=e-it_x2$で例証した対角展開の非クリフォードコストを比較する。
論文 参考訳（メタデータ） (2026-04-29T15:25:08Z) - CircuitSynth: Reliable Synthetic Data Generation [44.80087038178069]
大規模言語モデル(LLM)は、しばしば幻覚、論理的不整合、構造化された生成をタスクする場合のモード崩壊に悩まされる。
既存のアプローチ、例えば、プロンプトや検索強化ジェネレーションは、言語表現性と、妥当性とカバレッジに関する正式な保証のバランスをとるメカニズムを欠いている。
サーキットシンス(Circuit Synth)は,表面実現から意味論的推論を分離する新しいニューロシンボリックフレームワークである。
論文 参考訳（メタデータ） (2026-04-11T09:18:52Z) - Exact Structural Abstraction and Tractability Limits [0.0]
正確な正確性は、誘導されたクラス $s sim_R simation' iff MathrmAdm_R(s)$ にのみ依存する。
決定、探索、近似、統計的、ランダム化された地平線、分布保証は全て同じ商-回復問題に還元される。
論文 参考訳（メタデータ） (2026-04-08T17:59:47Z) - On the Convergence of Single-Loop Stochastic Bilevel Optimization with Approximate Implicit Differentiation [44.084531611147305]
単一ループ近似インプリシト差分法(SSAID)アルゴリズムの洗練された収束解析を行う。
i) 最適な$mathcalO(-2)$最先端のマルチループメソッドのレートと一致し、 (ii) $-dependenceの最初の明示的できめ細かい特徴を提供する。
論文 参考訳（メタデータ） (2026-02-27T03:12:08Z) - The nature of loops in programming [37.48416208168878]
プログラムのセマンティクスと検証では、ループに関する推論は2つの異なる数学的引数を生成する必要があるため複雑である。
単一かつ単純な定義が可能で、この分割を取り除くことができる。
ループが正しいことを証明するには、不変量と不変量を考案する必要はない。
関係を識別するのに十分であり、部分的正当性と終了の両方をもたらす。
論文 参考訳（メタデータ） (2025-04-10T20:58:55Z) - Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
我々は$f$-divergence-regularized offline policy learningを分析する。
逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。
これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
論文 参考訳（メタデータ） (2025-02-09T22:14:45Z) - Covariant Quantum Error-Correcting Codes with Metrological Entanglement Advantage [1.6018724979340826]
テンソル積 SU(2) の既約表現の基底の部分集合が、U(1) 論理ゲートを持つ近似量子誤り訂正符号を形成することを示す。
センサパラメータがU(1)論理ゲートのジェネレータに結合する場合、この符号の族は、標準量子限界を超える量子情報を持つプローブ状態を保護していることを示す。
論文 参考訳（メタデータ） (2024-09-30T17:59:01Z) - Some consequences of Sica's approach to Bell's inequalities [55.2480439325792]
ルイ・シカ(Louis Sica)は、ベルの不等式は、あるステーションで観測された結果の時系列が、他のステーションの設定が変更されても変化しないという仮説から導いた。
本稿では,Sicaのアプローチを非理想的効率と実時間構造に拡張する。
論文 参考訳（メタデータ） (2024-03-05T13:59:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。