論文の概要: A Verifier Hierarchy
- arxiv url: http://arxiv.org/abs/2507.23504v1
- Date: Thu, 31 Jul 2025 12:42:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-01 17:19:09.737014
- Title: A Verifier Hierarchy
- Title（参考訳）: 検証階層
- Authors: Maurits Kaptein,
- Abstract要約: 言語固有の検証時間を (f(n)) から (g(n)) に短縮するには,少なくとも (Omega(log(f(n) / g(n)))) の長さの証明書が必要であることを示す。
この定理は証明複雑性に基づいた自然な階層を誘導する。
- 参考スコア（独自算出の注目度）: 1.006218778776515
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We investigate the trade-off between certificate length and verifier runtime. We prove a Verifier Trade-off Theorem showing that reducing the inherent verification time of a language from \(f(n)\) to \(g(n)\), where \(f(n) \ge g(n)\), requires certificates of length at least \(\Omega(\log(f(n) / g(n)))\). This theorem induces a natural hierarchy based on certificate complexity. We demonstrate its applicability to analyzing conjectured separations between complexity classes (e.g., \(\np\) and \(\exptime\)) and to studying natural problems such as string periodicity and rotation detection. Additionally, we provide perspectives on the \(\p\) vs. \(\np\) problem by relating it to the existence of sub-linear certificates.
- Abstract（参考訳）: 本稿では,証明書の長さと検証実行時のトレードオフについて検討する。
ここでは、言語固有の検証時間を \(f(n)\) から \(g(n)\) に減少させる検証トレードオフ定理を証明し、少なくとも \(\Omega(\log(f(n) / g(n))\) の長さの証明書を必要とする。
この定理は証明複雑性に基づいた自然な階層を誘導する。
本稿では,複雑性クラス (eg , \(\np\) と \(\exptime\)) 間の予測された分離を解析し,弦周期性や回転検出などの自然問題の研究に有効であることを示す。
さらに、準線形証明書の存在を関連づけることで、 \(\p\) 対 \(\np\) 問題に対する視点を提供する。
関連論文リスト
- On the query complexity of unitary channel certification [0.0]
ユニタリチャネルの正しい機能を証明することは、信頼できる量子情報処理への重要なステップである。
量子メモリを必要としない非コヒーレントなアルゴリズム-$Omega(d/varepsilon2)$クエリは、既知の上限値と一致することを示す。
論文 参考訳（メタデータ） (2025-07-23T06:51:33Z) - Critical Thinking: Which Kinds of Complexity Govern Optimal Reasoning Length? [72.70486097967124]
決定論的有限オートマトン(DFAs)を用いたフレームワークの定式化
正しい解を生成する確率が最大になるような推論トークンが最適に存在することを示す。
新たな問題に対する推論トークンの最適個数を予測し、最適でない回答をフィルタリングすることで、一貫した精度の向上が得られる。
論文 参考訳（メタデータ） (2025-04-02T17:45:58Z) - MathGAP: Out-of-Distribution Evaluation on Problems with Arbitrarily Complex Proofs [80.96119560172224]
MathGAPは、それらの算術的証明構造に関する仕様に従って、問題文と連鎖推論トレースを生成する。
MathGAP を用いて, LLM はより深く, より広くなるにつれて, 性能が著しく低下することがわかった。
論文 参考訳（メタデータ） (2024-10-17T12:48:14Z) - How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions [0.0]
本研究では,確率的検証器が解析結果がほぼ正しいことを確認するための証明システムについて検討する。
未知の分布が要求される特性を持っていることを検証する。
我々の主な貢献は、検証者と信頼できない証明者との間の対話的プロトコルであり、任意のプロパティを検証するのに使用できる。
論文 参考訳（メタデータ） (2024-09-10T15:37:23Z) - Deciding branching hyperproperties for real time systems [1.1892416745067433]
リアルタイムシステムのセキュリティ特性は、しばしば超越性についての推論を伴う。
このような特性の例としては、情報フロー、サイドチャネルアタック、サービスレベルの合意などがある。
論文 参考訳（メタデータ） (2024-05-20T15:21:12Z) - $O_2$ is a multiple context-free grammar: an implementation-, formalisation-friendly proof [0.0]
それらを生成することができる文法の表現力に応じて言語を分類することは、計算言語学における根本的な問題である。
本稿では,各証明が検証された(すなわち,証明支援者によってチェックされる)アルゴリズムに繋がるかどうかを,MCFGを通して解析できるかどうかを体系的に研究する,計算的および証明理論的な視点から,既存の証明を解析する。
論文 参考訳（メタデータ） (2024-05-15T14:51:11Z) - Real-time Regular Expression Matching [65.268245109828]
本稿では,有限状態オートマトン,正規表現マッチング,パターン認識,指数的爆破問題について述べる。
本稿では,正規言語の複雑なクラスに対する指数的爆破問題に対する理論的およびハードウェア的解法を提案する。
論文 参考訳（メタデータ） (2023-08-20T09:25:40Z) - A simple geometric proof for the benefit of depth in ReLU networks [57.815699322370826]
本論文では, 多層フィードフォワードネットワークにおける深度の利点を, 整流活性化(深度分離)により証明する。
我々は、線形深さ($m$)と小さな定数幅($leq 4$)を持つ具体的なニューラルネットワークを示し、問題をゼロエラーで分類する。
論文 参考訳（メタデータ） (2021-01-18T15:40:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。