論文の概要: Representative Sets in Propositional Abduction
- arxiv url: http://arxiv.org/abs/2607.21183v1
- Date: Thu, 23 Jul 2026 11:14:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-24 18:26:25.380047
- Title: Representative Sets in Propositional Abduction
- Title（参考訳）: 前置的棄却における代表的集合
- Abstract要約: 命題推論問題は、非単調推論のよく知られた形式である。
我々は、与えられた説明の集合 S が他の説明を表現できるかどうかを問うような関連する表現問題を考える。
- 参考スコア（独自算出の注目度）: 7.028906373498561
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The propositional abduction problem is a well-known form of non-monotonic reasoning where we are asked to find an explanation of a given manifestation. Recently, there has been an influx of results asking more refined questions about the solution space rather than only individual solutions. For example, we might be interested in finding two solutions that are sufficiently far from each other (diverse solutions) in the solution space. In this paper we consider a related representation question where we ask if a given set of explanations S can represent any other explanation (that is, whether their symmetric difference is smaller than a given k). We first study this problem from a classical complexity perspective and obtain a complete classification. While only a handful of cases are tractable, the increase in complexity compared to classical abduction is often smaller than expected. We then study the parameterized complexity for several parameters and obtain new tractable and hard cases. Interestingly, a full parameterized complexity classification would require resolving the parameterized complexity of the covering radius problem from coding theory. To the best of our knowledge, no useful relationship between coding theory and non-monotonic reasoning has previously been established, but such connections seemingly become important when asking more complex questions about solution spaces.
- Abstract（参考訳）: 命題推論問題は、与えられた表現の説明を求める非単調推論のよく知られた形式である。
最近、個々の解だけでなく、解空間についてより洗練された質問をする結果が数多く出回っている。
例えば、解空間において、互いに十分に遠く離れた2つの解(様々な解)を見つけることに興味があるかもしれない。
本稿では、与えられた説明の集合 S が他の説明(つまり、それらの対称差が与えられた k よりも小さいかどうか)を表現できるかどうかを問う、関連する表現問題を考える。
まず、この問題を古典的な複雑性の観点から研究し、完全な分類を得る。
難治性のケースはごくわずかだが、古典的な誘拐と比較して複雑さが増すことは、しばしば予想より小さい。
次に、パラメータ化複雑性をいくつかのパラメータで研究し、新しい抽出可能な難易度と難易度を求める。
興味深いことに、完全なパラメータ化複雑性分類は、符号化理論から被覆半径問題のパラメータ化複雑性を解く必要がある。
我々の知る限りでは、符号化理論と非単調推論との有用な関係は確立されていないが、解空間に関するより複雑な質問を行う際には、そのような関係が重要であるように思われる。
関連論文リスト
- Complexity of Faceted Explanations in Propositional Abduction [6.674752821781092]
帰納的推論は、観察された症状や症状を説明することを目的とした、一般的な非単調なパラダイムである。
命題推論では、命題式による知識の特定に焦点をあてる。
意思決定とカウントの間の推論を検討し、説明をよりよく理解できるようにします。
論文 参考訳（メタデータ） (2025-07-20T13:50:26Z) - Why this and not that? A Logic-based Framework for Contrastive Explanations [4.3871352596331255]
対照的な説明に関連するいくつかの標準的な問題を定義し、それぞれが'なぜPはQではない'という形式の疑問に答える。
P と Q の両方の問題を計算し、その差を明示的に比較する。
我々の枠組みは、文献における既存の対照的な説明の基数-最小バージョンを捉えていることを示す。
論文 参考訳（メタデータ） (2025-07-11T09:55:04Z) - A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds [6.6362553223890535]
我々は、見過ごされているように見えるが自然なパラメータ n の下で、難解な誘引問題の複雑さを分析する。
SigmaP$ と NP- および coNP-完全 フラグメントに対していくつかの正の値が得られる。
我々はこれを低い境界で補い、多くのフラグメントは(強い)指数時間仮説の下で改善を除外する。
論文 参考訳（メタデータ） (2025-05-15T11:56:19Z) - Syzygy of Thoughts: Improving LLM CoT with the Minimal Free Resolution [59.39066657300045]
CoT(Chain-of-Thought)は、問題を逐次ステップに分解することで、大きな言語モデル(LLM)の推論を促進する。
思考のシジー(Syzygy of Thoughts, SoT)は,CoTを補助的,相互関連的な推論経路を導入して拡張する新しいフレームワークである。
SoTはより深い論理的依存関係をキャプチャし、より堅牢で構造化された問題解決を可能にする。
論文 参考訳（メタデータ） (2025-04-13T13:35:41Z) - Critical Thinking: Which Kinds of Complexity Govern Optimal Reasoning Length? [72.70486097967124]
決定論的有限オートマトン(DFAs)を用いたフレームワークの定式化
正しい解を生成する確率が最大になるような推論トークンが最適に存在することを示す。
新たな問題に対する推論トークンの最適個数を予測し、最適でない回答をフィルタリングすることで、一貫した精度の向上が得られる。
論文 参考訳（メタデータ） (2025-04-02T17:45:58Z) - MathGAP: Out-of-Distribution Evaluation on Problems with Arbitrarily Complex Proofs [80.96119560172224]
MathGAPは、それらの算術的証明構造に関する仕様に従って、問題文と連鎖推論トレースを生成する。
MathGAP を用いて, LLM はより深く, より広くなるにつれて, 性能が著しく低下することがわかった。
論文 参考訳（メタデータ） (2024-10-17T12:48:14Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Successive Prompting for Decomposing Complex Questions [50.00659445976735]
最近の研究は、大規模言語モデル(LM)の機能を活用して、数ショットで複雑な質問応答を行う。
そこでは、複雑なタスクを単純なタスクに繰り返し分解し、それを解決し、最終解を得るまでプロセスを繰り返します。
我々の最良のモデル(逐次プロンプト付き)は、DROPデータセットの数ショットバージョンにおいて、5%の絶対F1の改善を実現します。
論文 参考訳（メタデータ） (2022-12-08T06:03:38Z) - Complexity-Based Prompting for Multi-Step Reasoning [72.0057198610614]
大規模言語モデルに対して,多段階推論を行うための課題について検討する。
中心的な疑問は、どの推論例が最も効果的なプロンプトを作るかである。
多段階推論のためのシンプルで効果的な例選択方式である複雑性ベースのプロンプトを提案する。
論文 参考訳（メタデータ） (2022-10-03T05:33:27Z) - A Mutual Information Maximization Approach for the Spurious Solution
Problem in Weakly Supervised Question Answering [60.768146126094955]
弱々しい教師付き質問応答は通常、最終的な答えのみを監督信号として持つ。
偶然に正解を導出する刺激的な解が多数存在するかもしれないが、そのような解の訓練はモデルの性能を損なう可能性がある。
本稿では,質問応答対と予測解間の相互情報の最大化により,このような意味的相関を明示的に活用することを提案する。
論文 参考訳（メタデータ） (2021-06-14T05:47:41Z) - A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
我々の懸念は、標準的なデータベースクエリへの記述とそれらの最適な書き換えを介し、クエリに応答する際のデータ複雑さを効率的に決定することである。
我々は、疎結合シロップ(d-シロップ)と呼ばれるブール共役型クエリに焦点を当てる。
一部のd-シロップは指数的な大きさの分解能しか持たないが、そのうちのいくつかは二重指数サイズの正存在量書き換えと単帰的データログ書き換えのみである。
論文 参考訳（メタデータ） (2020-06-07T14:47:07Z) - Discriminative Learning via Adaptive Questioning [6.378513792050356]
本稿では,候補の能力を複数のカテゴリの1つに最適に分類する,適応的な質問列を設計する問題を考察する。
候補の能力は未知のパラメータとしてモデル化され、質問の難易度とともに、s/h が質問に正しく答えられる可能性を決定する。
論文 参考訳（メタデータ） (2020-04-11T16:50:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。