論文の概要: Epistemic Logic Programs: Non-Ground and Counting Complexity

• arxiv url: http://arxiv.org/abs/2503.04731v1
• Date: Fri, 31 Jan 2025 20:08:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-16 11:45:16.449776
• Title: Epistemic Logic Programs: Non-Ground and Counting Complexity
• Title（参考訳）: 疫学論理プログラム:非集合的・数的複雑度
• Authors: Thomas Eiter, Johannes K. Fichte, Markus Hecher, Stefan Woltran,
• Abstract要約: 疫学論理プログラム(ELP)は、ASPを拡張して全てのまたはいくつかの回答セットを推論する。 本稿では,非基底型ELPの複雑性を確立する。
• 参考スコア（独自算出の注目度）: 32.575043686973224
• License:
• Abstract: Answer Set Programming (ASP) is a prominent problem-modeling and solving framework, whose solutions are called answer sets. Epistemic logic programs (ELP) extend ASP to reason about all or some answer sets. Solutions to an ELP can be seen as consequences over multiple collections of answer sets, known as world views. While the complexity of propositional programs is well studied, the non-ground case remains open. This paper establishes the complexity of non-ground ELPs. We provide a comprehensive picture for well-known program fragments, which turns out to be complete for the class NEXPTIME with access to oracles up to \Sigma^P_2. In the quantitative setting, we establish complexity results for counting complexity beyond #EXP. To mitigate high complexity, we establish results in case of bounded predicate arity, reaching up to the fourth level of the polynomial hierarchy. Finally, we provide ETH-tight runtime results for the parameter treewidth, which has applications in quantitative reasoning, where we reason on (marginal) probabilities of epistemic literals.
• Abstract（参考訳）: 解答セットプログラミング(ASP)は、解答セットと呼ばれる、卓越した問題モデリングと解決のフレームワークである。 疫学論理プログラム(ELP)は、ASPを拡張して全てのまたはいくつかの回答セットを推論する。 ELPに対する解決策は、ワールドビューとして知られる複数の回答セットの集合に対する結果と見なすことができる。 命題プログラムの複雑さはよく研究されているが、非地上の場合はまだ未解決である。 本稿では,非基底型ELPの複雑性を確立する。 Sigma^P_2 までのオーラクルにアクセス可能な NEXPTIME クラスに対して,プログラムフラグメントの包括的図を提供する。 定量的な設定では、#EXPを超えて複雑性をカウントする複雑性結果を確立する。 高複雑性を緩和するため、有界述語アリティの場合の結果を確立し、多項式階層の4レベルまで到達する。 最後に、パラメータツリー幅に対してETH-tightランタイム結果を提供し、定量推論に応用でき、そこでは、てんかんリテラルの(疑似)確率を推論する。

関連論文リスト

• ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning [92.76959707441954]
  我々はLLM推論性能を評価するための総合的な評価フレームワークであるZebraLogicを紹介した。 ZebraLogicは、制御可能で定量化可能な複雑さを持つパズルの生成を可能にする。 その結果,複雑性が増大するにつれて,精度が著しく低下することが明らかとなった。
  論文  参考訳（メタデータ） (2025-02-03T06:44:49Z)
• The Computational Complexity of Circuit Discovery for Inner Interpretability [0.30723404270319693]
  我々は古典的およびパラメータ化された計算複雑性理論を用いて回路発見を研究する。 私たちの発見は、難しい複雑さの風景を明らかにします。 このフレームワークは、解釈可能性クエリの範囲と限界を理解するのに役立ちます。
  論文  参考訳（メタデータ） (2024-10-10T15:22:48Z)
• Advancing Algorithmic Approaches to Probabilistic Argumentation under the Constellation Approach [0.0]
  完全拡張である引数の集合の確率を計算する複雑なタスクのアルゴリズムを開発する。 実験的評価は我々のアプローチの可能性を示唆している。
  論文  参考訳（メタデータ） (2024-07-06T12:08:38Z)
• Extended Version of: On the Structural Hardness of Answer Set Programming: Can Structure Efficiently Confine the Power of Disjunctions? [21.10339925217772]
  プログラムのルール構造上での解離的ASPの構造パラメータの分類に対処する。 我々は、その範囲で最も顕著なパラメータに対して、二重指数下界を提供する。 本研究は, 通常のプログラムから解離プログラムへの新規な縮小に頼って, 深部硬度調査を行う。
  論文  参考訳（メタデータ） (2024-02-05T21:51:36Z)
• When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
  本稿では,コードと推論能力の相関性を測定するために,複雑性に富んだ推論スコア(CIRS)を提案する。 具体的には、抽象構文木を用いて構造情報をエンコードし、論理的複雑性を計算する。 コードはhttps://github.com/zjunlp/EasyInstructのEasyInstructフレームワークに統合される。
  論文  参考訳（メタデータ） (2023-08-29T17:22:39Z)
• Successive Prompting for Decomposing Complex Questions [50.00659445976735]
  最近の研究は、大規模言語モデル(LM)の機能を活用して、数ショットで複雑な質問応答を行う。 そこでは、複雑なタスクを単純なタスクに繰り返し分解し、それを解決し、最終解を得るまでプロセスを繰り返します。 我々の最良のモデル(逐次プロンプト付き)は、DROPデータセットの数ショットバージョンにおいて、5%の絶対F1の改善を実現します。
  論文  参考訳（メタデータ） (2022-12-08T06:03:38Z)
• Will Bilevel Optimizers Benefit from Loops [63.22466953441521]
  AID-BiOとITD-BiOの2つの一般的な双レベルマトリクスは、自然に1つまたは2つのサブプロブレムを解決する。 AID-BiO と ITD-BiO の両ループ実装選択に適用可能な統合収束解析をまず確立する。
  論文  参考訳（メタデータ） (2022-05-27T20:28:52Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。 特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。 以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
  論文  参考訳（メタデータ） (2022-02-08T16:39:57Z)
• Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs [22.39203220587435]
  本稿では,このような量的推論問題に対処するために必要な基礎的数え上げ問題を効率的に解くことのできる,新しいシステムを提案する。 本システムでは,木幅をグラフベースで表し,ELPプログラムの抽象表現(グラフ)を反復的に探索し,精算する。 私たちのアプローチは、最近導入された既存のシステムと競合しています。
  論文  参考訳（メタデータ） (2021-08-06T09:46:34Z)
• Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
  この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。 提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
  論文  参考訳（メタデータ） (2020-06-22T17:58:54Z)
• Structural Decompositions of Epistemic Logic Programs [29.23726484912091]
  認識論理プログラム(ELP)は標準解集合プログラミング(ASP)の一般的な一般化である 本研究では, 木幅境界で構造特性を示すELPに対して, 線形時間で中心的な問題を解くことができることを示す。 また、これらの境界に従属する完全な動的プログラミングアルゴリズムも提供します。
  論文  参考訳（メタデータ） (2020-01-13T13:16:13Z)

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

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