論文の概要: A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds

• arxiv url: http://arxiv.org/abs/2505.10201v1
• Date: Thu, 15 May 2025 11:56:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-16 22:29:06.302521
• Title: A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds
• Title（参考訳）: 命題アブダクションに関する細粒度複雑度ビュー -- アルゴリズムと下界
• Authors: Victor Lagerkvist, Mohamed Maizia, Johannes Schmidt,
• Abstract要約: 我々は、見過ごされているように見えるが自然なパラメータ n の下で、難解な誘引問題の複雑さを分析する。 SigmaP$ と NP- および coNP-完全 フラグメントに対していくつかの正の値が得られる。 我々はこれを低い境界で補い、多くのフラグメントは(強い)指数時間仮説の下で改善を除外する。
• 参考スコア（独自算出の注目度）: 6.6362553223890535
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Boolean satisfiability problem (SAT) is a well-known example of monotonic reasoning, of intense practical interest due to fast solvers, complemented by rigorous fine-grained complexity results. However, for non-monotonic reasoning, e.g., abductive reasoning, comparably little is known outside classic complexity theory. In this paper we take a first step of bridging the gap between monotonic and non-monotonic reasoning by analyzing the complexity of intractable abduction problems under the seemingly overlooked but natural parameter n: the number of variables in the knowledge base. We obtain several positive results for $\Sigma^P_2$- as well as NP- and coNP-complete fragments, which implies the first example of beating exhaustive search for a $\Sigma^P_2$-complete problem (to the best of our knowledge). We complement this with lower bounds and for many fragments rule out improvements under the (strong) exponential-time hypothesis.
• Abstract（参考訳）: ブール充足可能性問題(英: Boolean satisfiability problem、SAT)は、単調推論のよく知られた例であり、高速解法による厳密な実践的関心を、厳密な微細な複雑さの結果によって補う。 しかし、非単調な推論(eg, abductive reasoning)においては、古典的複雑性理論以外ではほとんど知られていない。 本稿では, 単調な推論と非単調な推論のギャップを埋める第一歩として, 一見見過ごされながら自然なパラメータn, 知識ベースにおける変数数に基づいて, 難解な推論問題の複雑性を解析する。 我々は、$\Sigma^P_2$-およびNP-およびcoNP-完全フラグメントに対していくつかの肯定的な結果を得る。 我々はこれを低い境界で補い、多くのフラグメントは(強い)指数時間仮説の下で改善を除外する。

関連論文リスト

• The complexity of entanglement embezzlement [0.0]
  プロセスの任意の精度を実現する状態列を用いて,エンベゾルメントの回路複雑性について検討する。 回路の複雑さは、完全なエンベゾルメントの物理的障害として働くことを示唆する。
  論文  参考訳（メタデータ） (2024-10-24T18:00:33Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Advancing Algorithmic Approaches to Probabilistic Argumentation under the Constellation Approach [0.0]
  完全拡張である引数の集合の確率を計算する複雑なタスクのアルゴリズムを開発する。 実験的評価は我々のアプローチの可能性を示唆している。
  論文  参考訳（メタデータ） (2024-07-06T12:08:38Z)
• A New Approach to Generic Lower Bounds: Classical/Quantum MDL, Quantum Factoring, and More [1.1893324664457547]
  本稿では,古典的および量子的設定における暗号問題の解法における汎用的アプローチの限界について検討する。 両方のモデルにおいて、両方のモデルの量子的下界は、ある種の古典的な前処理を可能にする。
  論文  参考訳（メタデータ） (2024-02-17T13:00:47Z)
• Learning to Select and Rank from Choice-Based Feedback: A Simple Nested Approach [10.293894471295205]
  本研究では、動的アソートによる選択に基づくフィードバックから学習する際のランク付けと選択の問題について検討する。 両学習目標に対して,新しい,シンプルなアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-07-13T05:05:30Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。 この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。 さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
  論文  参考訳（メタデータ） (2022-06-02T15:21:55Z)
• Logic Embeddings for Complex Query Answering [56.25151854231117]
  skolemisationを用いて効率的なクエリのための存在変数を排除する、複雑なクエリを組み込む新しいアプローチであるlogic embeddedsを提案する。 論理組込みは,大規模で不完全な知識グラフ上でのクエリ応答において競争的に高速かつ正確であり,否定的問合せよりも優れており,特に回答の不確かさのモデリングが向上している。
  論文  参考訳（メタデータ） (2021-02-28T07:52:37Z)
• A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
  我々の懸念は、標準的なデータベースクエリへの記述とそれらの最適な書き換えを介し、クエリに応答する際のデータ複雑さを効率的に決定することである。 我々は、疎結合シロップ(d-シロップ)と呼ばれるブール共役型クエリに焦点を当てる。 一部のd-シロップは指数的な大きさの分解能しか持たないが、そのうちのいくつかは二重指数サイズの正存在量書き換えと単帰的データログ書き換えのみである。
  論文  参考訳（メタデータ） (2020-06-07T14:47:07Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。 ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
  論文  参考訳（メタデータ） (2020-04-25T05:45:59Z)

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

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