論文の概要: Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach

• arxiv url: http://arxiv.org/abs/2605.12073v1
• Date: Tue, 12 May 2026 13:00:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-13 21:48:56.868709
• Title: Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach
• Title（参考訳）: QBFのためのクラス削除バックドア:パラメータ化複素性アプローチ
• Authors: Leif Eriksson, Victor Lagerkvist, Sebastian Ordyniak, George Osipov, Fahad Panolan, Mateusz Rychlicki,
• Abstract要約: 定量化ブール式(QBF)の妥当性を検討する。 抽出可能なクラスに到達する前に削除しなければならない節の変数数という新しいパラメータを提案する。 CCバックドアが$k$であるなら、FPT時間でQBFを解くことに興味があります。
• 参考スコア（独自算出の注目度）: 19.400202883397537
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Determining the validity of a quantified Boolean formula (QBF) is a PSPACE-complete problem with rich expressive power. Despite interest in efficient solvers, there is, compared to problems in NP, a lack of positive theoretical results, and in the parameterized complexity setting one often has to restrict the quantifier prefix (e.g., bounding alternations) to obtain fixed parameter tractability (FPT). We propose a new parameter: the number of variables in clauses that has to be removed before reaching a tractable class (a clause covering (CC) backdoor). We are then interested in solving QBF in FPT time given a CC-backdoor of size $k$. We consider the three classical, tractable cases of QBF as base classes: Horn, 2-CNF, and linear equations. We establish W[1]-hardness for Horn but prove FPT for the others, and prove that in a precise, algebraic sense, we are only missing one important case for a full dichotomy. Our algorithms are non-trivial and depend on propagation, and Gaussian elimination, respectively, and are comparably unexplored for QBF.
• Abstract（参考訳）: 量化ブール式(QBF)の妥当性を決定することは、豊かな表現力を持つPSPACE完全問題である。 効率的な解法には興味があるが、NPの問題と比較すると、正の理論的結果の欠如があり、パラメータ化複雑性設定では、固定パラメータトラクタビリティ(FPT)を得るために、量化子プレフィックス(例えば、境界変更)を制限しなければならないことが多い。 抽出可能なクラス(CCのバックドアをカバーする節)に到達する前に削除しなければならない節の変数の数。 CCバックドアが$k$であるなら、FPT時間でQBFを解くことに興味があります。 古典的かつトラクタブルなQBFの3つのケースを基底クラスとして考える: Horn, 2-CNF, 線形方程式。 我々は、Hhorn に対して W[1]-ハードネスを確立するが、他の部分に対して FPT を証明し、正確に代数的な意味では、完全二分法において重要なケースが一つしか欠落していることを証明している。 我々のアルゴリズムは、伝播に頼らず、それぞれガウスの除去に依存しており、QBFでは比較不能である。

関連論文リスト

• Decoded Quantum Interferometry for Weighted Optimization Problems [6.4675604105664]
  復号化量子干渉法(Decoded Quantum Interferometry, DQI)は、最近導入された復号化量子最適化法である。 元々の定式化において、DQIはすべての制約を均一に扱い、興味のあるほとんどの最適化問題に存在する重み構造を利用できない。 我々は、重み付き最適化問題に対するDQIの理論を開発し、重み付きMax-LINSAT問題に焦点を当てる。
  論文  参考訳（メタデータ） (2026-05-11T14:45:46Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Deciding Whether a C-Q Channel Preserves a Bit is QCMA-Complete [0.0]
  古典量子(C-Q)チャネルが1つの古典ビットを正確に保存できるかどうかを決定することはQCMA完全であることを示す。 この「ビット保存」問題は、C-Qチャネル上の直交制約付き最適化タスクの特別な場合である。
  論文  参考訳（メタデータ） (2025-08-14T14:03:38Z)
• Compilation and Fast Model Counting beyond CNF [31.620928650659586]
  本稿では,関数のクラスを効率的にd-DNNFに変換するか,あるいはコンパイルするかに関する理論的知識を強化する。 問題の制約は、すべての変数順序付けに対して、定数幅順序付きバイナリ決定図(OBDD)で表現可能なすべての関数である。 制約のサブファミリーに適用し,コンパイルを必要としないモデルカウントのためのより効率的なFPTアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-02-01T14:00:04Z)
• Solving Quantified Boolean Formulas with Few Existential Variables [19.221715574358207]
  QBF問題(Quantified Boolean formula)は、PSPACE完全性のアーキタイプとして一般的に見なされる重要な決定問題である。 本稿では,実数量化変数の数という,単純だが見過ごされたパラメータについて考察する。 次に、有界節長の共役正規形(CNF)のQBFインスタンスに適用可能な新しいFPTアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2024-05-10T14:07:29Z)
• General Boolean Formula Minimization with QBF Solvers [4.264192013842096]
  我々は任意の形式で同等の式を得るという問題に興味を持っている。 我々は、最小化アルゴリズムを適用して、元の公式の自然言語翻訳を生成する動機付けをしている。 我々はその問題を解決するための3つの可能な(実践的な)アプローチを分析する。
  論文  参考訳（メタデータ） (2023-03-12T12:08:58Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。 本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
  論文  参考訳（メタデータ） (2021-05-06T17:59:38Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。 ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
  論文  参考訳（メタデータ） (2020-04-25T05:45:59Z)
• Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting [81.70513857417106]
  CascadeBAIを設計し、分析する。これは、$K$アイテムのベストセットを見つけるアルゴリズムである。 CascadeBAIの時間的複雑さの上限は、決定的な分析課題を克服することによって導かれる。 その結果,カスケードBAIの性能は,時間的複雑性の低い境界の導出により,いくつかの実践的状況において最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-01-23T16:47:52Z)

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

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