論文の概要: Ineffectiveness for Search and Undecidability of PCSP Meta-Problems

• arxiv url: http://arxiv.org/abs/2504.04639v2
• Date: Sun, 13 Apr 2025 23:31:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-15 16:44:38.696373
• Title: Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
• Title（参考訳）: PCSPメタプロブレムの探索と不確定性
• Authors: Alberto Larrauri,
• Abstract要約: PCSPの最もよく知られたアルゴリズムは、そのエンフデシジョン変種のみを解き、それらがエンフサーチにも適応できるかどうかは不明である。 我々は、これらの解を適切な検索証明書に丸めることは、クラスTFNPのどの問題にも匹敵するほど難しいことを証明している。 我々のツールは,ミニオンを特徴とするアルゴリズムに適しており,メタプロブレムの判定不能な結果を証明するためにも使用できる。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: It is an open question whether the search and decision versions of promise CSPs are equivalent. Most known algorithms for PCSPs solve only their \emph{decision} variant, and it is unknown whether they can be adapted to solve \emph{search} as well. The main approaches, called BLP, AIP and BLP+AIP, handle a PCSP by finding a solution to a relaxation of some integer program. We prove that rounding those solutions to a proper search certificate can be as hard as any problem in the class TFNP. In other words, these algorithms are ineffective for search. Building on the algebraic approach to PCSPs, we find sufficient conditions that imply ineffectiveness for search. Our tools are tailored to algorithms that are characterized by minions in a suitable way, and can also be used to prove undecidability results for meta-problems. This way, we show that the families of templates solvable via BLP, AIP, and BLP+AIP are undecidable. Using the same techniques we also analyze several algebraic conditions that are known to guarantee the tractability of finite-template CSPs. We prove that several meta-problems related to cyclic polymorphims and WNUs are undecidable for PCSPs. In particular, there is no algorithm deciding whether a finite PCSP template (1) admits cyclic a polymorphism, (2) admits a WNU.
• Abstract（参考訳）: 有望なCSPの検索版と決定版が同等であるかどうかは、明らかな疑問である。 PCSP の最もよく知られたアルゴリズムは \emph{decision} の変種のみを解き、それらが \emph{search} の解にも適用できるかどうかは不明である。 BLP、AIP、BLP+AIPと呼ばれる主なアプローチは、整数プログラムの緩和に対する解を見つけることによってPCSPを扱う。 我々は、これらの解を適切な検索証明書に丸めることは、クラスTFNPのどの問題にも匹敵するほど難しいことを証明している。 言い換えれば、これらのアルゴリズムは検索には有効ではない。 PCSPの代数的アプローチに基づいて、探索に効果のない十分な条件を見出す。 我々のツールは,ミニオンを特徴とするアルゴリズムに適しており,メタプロブレムの判定不能な結果を証明するためにも使用できる。 このようにして、BLP、AIP、BLP+AIPを介して解決できるテンプレートのファミリーは決定不能であることを示す。 同じ手法を用いて、有限テンポレート CSP のトラクタビリティを保証することが知られているいくつかの代数的条件も解析する。 循環型ポリモルフィムやWNUに関連するいくつかのメタプロブレムがPCSPでは決定できないことが証明された。 特に、有限PCSPテンプレート(1)が巡回多型を許容するか、(2)は WNU を許容するかを決定するアルゴリズムは存在しない。

関連論文リスト

• Search Strategy Generation for Branch and Bound Using Genetic Programming [0.0]
  GP2S(Genetic Programming for Search Strategy)は,B&B検索戦略を自動生成する機械学習手法である。 我々は、SCIPソルバの標準手法、最近のグラフニューラルネットワークに基づく手法、手工芸品との比較を行った。 我々の手法は最良基準よりも2%遅く、SCIPを一貫して上回り、平均速度は11.3%に達する。
  論文  参考訳（メタデータ） (2024-12-12T16:57:46Z)
• Fast decision tree learning solves hard coding-theoretic problems [7.420043502440765]
  我々は、Ehrenfeucht と Haussler のアルゴリズムの改善により、$k$-NCP に対して$O(log n)$-approximation アルゴリズムが得られることを示す。 これは、$k$-NCPのアルゴリズムを設計するための新しい道、あるいはEhrenfeucht と Haussler のアルゴリズムの最適性を確立するための道と解釈できる。
  論文  参考訳（メタデータ） (2024-09-19T21:40:57Z)
• Universal Quantum Speedup for Branch-and-Bound, Branch-and-Cut, and Tree-Search Algorithms [13.152347996965297]
  混合プログラム(MIP)は、コンピュータサイエンス、オペレーションリサーチ、ファイナンシャルエンジニアリングに関心を持つ多くの最適化問題をモデル化する。 Branch-and-Cutアルゴリズムは、ブランチ・アンド・バウンド論理とカットプレーンルーチンを組み合わせることで、現代のMIPソルバのコアとなる。 本稿では,古典的分岐と境界のアルゴリズムを用いた量子アルゴリズムIncremental-Quantum-Branch-and-Boundを提案する。
  論文  参考訳（メタデータ） (2022-10-06T21:08:46Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Dynamic programming by polymorphic semiring algebraic shortcut fusion [1.9405875431318445]
  動的プログラミング(動的プログラミング、英: Dynamic Programming、DP)は、難解問題の効率的かつ正確な解法のためのアルゴリズム設計パラダイムである。 本稿では,セミリングに基づくDPアルゴリズムを体系的に導出するための厳密な代数形式について述べる。
  論文  参考訳（メタデータ） (2021-07-05T00:51:02Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Towards Meta-Algorithm Selection [78.13985819417974]
  インスタンス固有のアルゴリズム選択(AS)は、固定された候補集合からのアルゴリズムの自動選択を扱う。 メタアルゴリズムの選択は、いくつかのケースで有益であることを示す。
  論文  参考訳（メタデータ） (2020-11-17T17:27:33Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。 我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
  論文  参考訳（メタデータ） (2020-10-04T22:19:06Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Performance Analysis of Meta-heuristic Algorithms for a Quadratic Assignment Problem [6.555180412600522]
  二次代入問題 (QAP) はNPハード問題に属する最適化問題である。 ヒューリスティックスとメタヒューリスティックスアルゴリズムはこの問題の一般的な解法である。 本稿では,QAPの解法に異なるメタヒューリスティックアルゴリズムを適用するための比較研究の1つである。
  論文  参考訳（メタデータ） (2020-07-29T15:02:07Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)

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

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