概要 - TFNP内の階層：構成要素と崩壊
タイトル
TFNP内の階層：構成要素と崩壊
時間
2025-07-29 07:25:40
著者
{"Surendra Ghentiyala","Zeyong Li"}
カテゴリ
{cs.CC}
リンク
http://arxiv.org/abs/2507.21550v1
PDF リンク
http://arxiv.org/pdf/2507.21550v1
概要
この論文は、AとBがどちらもTFNP（全関数非決定的多項式時間）のサブクラスであるAB複雑性クラスを探求しています。著者たちは新しい定義を導入し、これらのクラスに関連するいくつかの定理を証明しています。 ### 主要な定義 * **AB**: 新しい複雑性クラスとして、問題Bのためのオラクルゲートを持つ回路問題Aに還元可能な全探索問題の集合として定義されています。 * **オラクルゲート**: 回路内に存在し、他の問題Bに対するクエリを実行し、Bの解を補助入力として提供するゲート。 * **C∗**: オラクル回路の評価をシミュレートする回路で、そのオラクルゲートの解を提供する補助入力として機能します。 ### 主要な結果 * **PPAPPA = PPA**: PPA階層が最初のレベルに収束し、PPAPPAがPPAに等しいことを示しています。 * **PLSPLS = PLS**: PLS階層が最初のレベルに収束し、PLSPLSがPLSに等しいことを示しています。 * **LOSSYLOSSY = LOSSY**: LOSSY階層が最初のレベルに収束し、LOSSYLOSSYがLOSSYに等しいことを示しています。 ### 含意 * **自己低さ**: 結果は、いくつかの古典的なTFNPサブクラスが自己低いことを示しており、その階層は最初のレベルに収束します。これは、TFNP内の計算問題を新しい方法で分類する新しい方法を提供します。 * **応用**: 著者たちは、これらの新しいTFNPサブクラスが、大きな素数を生成する問題のようなよく知られた問題の複雑性を研究するためにどのように適用できるかを示しています。 ### 意義 この論文は、TFNP複雑性クラスとその関係に対する理解に寄与しています。新しい定義と結果は、TFNP内の問題の複雑性を研究するための枠組みを提供し、暗号理論や複雑性理論などの分野における応用が期待されます。
推奨論文
可解性マッパー：パラメータ調整に基づく説明と検証エージェントを使用してLLMエンブッディング空間を図示する
HairCUP: 3D高斯アバターの髪の構成ユニバーサル事前情報
モデリング（デオンティック）モーダル演算子とs(CASP)ゴール指向的な宣言的な答えセットプログラミングシステム Translation: モデリング（デオンティック）モーダル演算子とs(CASP)ゴール指向的な宣言的な答えセットプログラミングシステム
監督量子画像処理
非構造データからのパーソナライズされた治療効果推定
SpeechIQ：音声理解の大規模言語モデルにおける認知レベルにわたる音声知能指数
Ultra3D：部分注意での効率的で高精度な3D生成
構造力駆動型のトポロジー最適化における適応的な细化と粗化
ApproxGNN：近似計算のためのデザイン空間探索におけるパラメータ予測のための事前トレーニングGNN