ランダム化クエリ複雑性は証明書複雑性を上回ることができる
Randomized query complexity can beat certificate complexity (arxiv.org)
要約
計算複雑性理論における長年の未解決問題に対し、ランダム化クエリ複雑性（R(f)）と証明書複雑性（C(f)）の間にR(f) << C(f)となるブール関数が存在するかどうかが問われていました。本研究では、R(f) = O~(sqrt{C(f)})となる関数を構築し、これは対数因子を除いて最適であることが示されました。さらに、この関数は量子クエリ複雑性Q(f)についてもQ(f) = O~(C(f)^{1/4})となり、これもほぼ最適であることが示唆されています。
全文翻訳
コンピュータサイエンス > 計算複雑性
arXiv:2609.15063 (cs)
[2026年9月14日 投稿]
タイトル: ランダム化クエリ複雑性は証明書複雑性を上回ることができる
著者: Shalev Ben-David, Robin Kothari
Shalev Ben-Davidと他の1名の著者による論文「Randomized query complexity can beat certificate complexity」のPDFを表示
要旨: クエリ複雑性における長年の未解決問題は、R(f) と C(f) がそれぞれ有界誤差ランダム化クエリ複雑性および証明書複雑性を表すとき、全域ブール関数 f に対して R(f) << C(f) となるものが存在するかどうかを問うものです。我々は、R(f) = O~(sqrt{C(f)}) となる関数を構築しました。これは対数因子を除けば最適です。同じ関数は $Q(f) = O~(C(f)^{1/4})$ という、ほぼ最適な有界誤差量子クエリ複雑性も持ちます。
| コメント: | 6ページ |
| 件名: | 計算複雑性 (cs.CC); 量子物理学 (quant-ph) |
| 引用元: | arXiv:2609.15063 [cs.CC] |
| (またはこのバージョンについては arXiv:2609.15063v1 [cs.CC]) | |
| https://doi.org/10.48550/arXiv.2609.15063 DataCite経由のarXiv発行DOI |
投稿履歴
送信者: Robin Kothari
メールを表示
[v1] 月曜日, 2026年9月14日 05:29:42 UTC (9 KB)
全文リンク:
論文にアクセス
Shalev Ben-Davidと他の1名の著者による論文「Randomized query complexity can beat certificate complexity」のPDFを表示
追加機能
現在の閲覧コンテキスト:
cs.CC
以下で閲覧を変更:
参考文献と引用
読み込み中...
BibTeX形式の引用
読み込み中...
提供元:
ブックマーク
Bibliographic Tools
書誌情報および引用ツール
Bibliographic Explorer トグル
Bibliographic Explorer (Explorerとは?)
Connected Papers トグル
Connected Papers (Connected Papersとは?)
Litmaps トグル
Litmaps (Litmapsとは?)
scite.ai トグル
scite Smart Citations (Smart Citationsとは?)
コード、データ、メディア
この論文に関連するコード、データ、メディア
alphaXiv トグル
alphaXiv (alphaXivとは?)
コードへのリンク トグル
CatalyzeX Code Finder for Papers (CatalyzeXとは?)
DagsHub トグル
DagsHub (DagsHubとは?)
GotitPub トグル
Gotit.pub (GotitPubとは?)
Huggingface トグル
Hugging Face (Huggingfaceとは?)
ScienceCast トグル
ScienceCast (ScienceCastとは?)
デモ
デモ
Replicate トグル
Replicate (Replicateとは?)
Spaces トグル
Hugging Face Spaces (Spacesとは?)
Spaces トグル
TXYZ.AI (TXYZ.AIとは?)
関連論文
レコメンダーおよび検索ツール
Influence Flowerへのリンク
Influence Flower (Influence Flowersとは?)
Core recommender トグル
CORE Recommender (COREとは?)
- 著者
- 会場
- 機関
- トピック
arXivLabsについて
arXivLabs: コミュニティ協力者との実験的プロジェクト
arXivLabsは、協力者がarXivのウェブサイト上で直接新しいarXivの機能を開発・共有できるフレームワークです。
arXivLabsと協力する個人および組織は、オープンさ、コミュニティ、卓越性、ユーザーデータプライバシーという我々の価値観を受け入れ、承認しています。arXivはこの価値観にコミットしており、それに準拠するパートナーのみと協力します。
arXivコミュニティに価値をもたらすプロジェクトのアイデアをお持ちですか？ arXivLabsについてさらに学ぶ。
この論文の著者のうち、推薦者は誰ですか? | MathJaxを無効にする (MathJaxとは?)