論文の概要: On the Complexity of Enumerating Prime Implicants from Decision-DNNF Circuits

• arxiv url: http://arxiv.org/abs/2301.13328v1
• Date: Mon, 30 Jan 2023 23:23:45 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-01 18:19:26.393903
• Title: On the Complexity of Enumerating Prime Implicants from Decision-DNNF Circuits
• Title（参考訳）: 決定-DNNF回路からの素命令列挙の複雑さについて
• Authors: Alexis de Colnet and Pierre Marquis
• Abstract要約: 本稿では,決定分解可能な否定正規回路(dec-DNNF)で表されるブール関数の素命令を列挙する問題EnumIPについて考察する。 出力列挙問題のクラスであるOutputPと、より正確にはインクリメンタル時間列挙問題のクラスであるIncPのクラスであることを示す。
• 参考スコア（独自算出の注目度）: 21.381877097979654
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem EnumIP of enumerating prime implicants of Boolean functions represented by decision decomposable negation normal form (dec-DNNF) circuits. We study EnumIP from dec-DNNF within the framework of enumeration complexity and prove that it is in OutputP, the class of output polynomial enumeration problems, and more precisely in IncP, the class of polynomial incremental time enumeration problems. We then focus on two closely related, but seemingly harder, enumeration problems where further restrictions are put on the prime implicants to be generated. In the first problem, one is only interested in prime implicants representing subset-minimal abductive explanations, a notion much investigated in AI for more than three decades. In the second problem, the target is prime implicants representing sufficient reasons, a recent yet important notion in the emerging field of eXplainable AI, since they aim to explain predictions achieved by machine learning classifiers. We provide evidence showing that enumerating specific prime implicants corresponding to subset-minimal abductive explanations or to sufficient reasons is not in OutputP.
• Abstract（参考訳）: 決定分解可能な否定正規形(dec-DNNF)回路で表されるブール関数の素命令を列挙する問題EnumIPを考える。 我々は列挙複雑性の枠組みの中でde-DNNFからEnumIPを研究し、出力多項式列挙問題のクラスであるOutputPにあることを証明し、より正確には多項式増分時間列挙問題のクラスであるIncPで証明する。 次に、生成すべき素因果関係にさらなる制限が課される2つの密接に関連するが、一見難しい列挙問題に焦点を当てる。 最初の問題では、サブセット最小の誘引的説明を表す素命令のみに関心を持ち、これはAIで30年以上研究されてきた概念である。 第2の問題は、機械学習分類器によって達成された予測を説明することを目的としているため、eXplainable AIの新興分野における近年の重要概念である十分な理由を表す素命令である。 サブセット最小誘引的説明や十分な理由に対応する特定の素命令を列挙することはアウトプットPにはないことを示す証拠を提供する。

関連論文リスト

• Probabilistic and Causal Satisfiability: the Impact of Marginalization [3.44747819522562]
  確率的・因果的言語で表される満足度問題に焦点をあてる。 線形言語はNPPP-, PSPACE-, NEXP完全満足度問題をもたらすことを示す。 また、与えられたベイズネットワーク、有向非巡回グラフ構造、あるいは小さなサイズに制限された制約付きモデルについても検討する。
  論文  参考訳（メタデータ） (2024-05-12T20:25:36Z)
• On Computing Probabilistic Abductive Explanations [30.325691263226968]
  最も広く研究されているAI(XAI)アプローチは正しくない。 PI説明は重要な欠点も示しており、最も目に見えるものはおそらくその大きさである。 本稿では,多くの広く使用されている分類器に対して,関連する集合を計算するための実践的アプローチについて検討する。
  論文  参考訳（メタデータ） (2022-12-12T15:47:10Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• An Algebraic-Geometry Approach to Prime Factorization [0.0]
  素因数分解のための新しいアルゴリズムは、暗号アルゴリズムの現在の実装に実践的な影響を与える可能性がある。 n/2以上のパラメータを効率的に評価できる多様体が存在することを示す。 ある場合、 n/2 以上のパラメータが与えられたとき、効率的に点を評価できる多様体が存在することを示す。
  論文  参考訳（メタデータ） (2022-09-23T15:31:07Z)
• On the Computation of Necessary and Sufficient Explanations [11.358487655918676]
  決定の背後にある完全な理由は、決定が下された理由を特徴付けるブール公式である。 本稿では、決定に必要な理由として、完全な理由の素因を言及する。 出力時間において最短の理由を列挙できるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-03-20T04:39:41Z)
• Polynomial unconstrained binary optimisation inspired by optical simulation [52.11703556419582]
  制約のないバイナリ最適化の問題を解決するために,光コヒーレントIsingマシンにヒントを得たアルゴリズムを提案する。 提案アルゴリズムを既存のPUBOアルゴリズムに対してベンチマークし,その優れた性能を観察する。 タンパク質の折り畳み問題や量子化学問題へのアルゴリズムの適用は、PUBO問題による電子構造問題の近似の欠点に光を当てる。
  論文  参考訳（メタデータ） (2021-06-24T16:39:31Z)
• Discrete Reasoning Templates for Natural Language Understanding [79.07883990966077]
  我々は,複雑な質問をより単純な質問に分解する手法を提案する。 事前定義された推論テンプレートの指示に従って最終回答を導出する。 我々のアプローチは、解釈可能でありながら最先端技術と競合し、監督をほとんど必要としないことを示す。
  論文  参考訳（メタデータ） (2021-04-05T18:56:56Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。 それらの構造的特性について検討する。
  論文  参考訳（メタデータ） (2020-12-01T13:53:23Z)
• A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
  我々の懸念は、標準的なデータベースクエリへの記述とそれらの最適な書き換えを介し、クエリに応答する際のデータ複雑さを効率的に決定することである。 我々は、疎結合シロップ(d-シロップ)と呼ばれるブール共役型クエリに焦点を当てる。 一部のd-シロップは指数的な大きさの分解能しか持たないが、そのうちのいくつかは二重指数サイズの正存在量書き換えと単帰的データログ書き換えのみである。
  論文  参考訳（メタデータ） (2020-06-07T14:47:07Z)
• From Checking to Inference: Actual Causality Computations as Optimization Problems [79.87179017975235]
  本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。 8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
  論文  参考訳（メタデータ） (2020-06-05T10:56:52Z)
• Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
  i) 任意の状態空間, (ii) 任意の行動空間, (iii) 任意の送信者のユーティリティ関数を用いて, 一般の状況下での公衆の説得問題を考察する。 任意の公的な説得問題に対して準多項式時間ビクテリア近似アルゴリズムを提案し、特定の設定でQPTASを出力する。
  論文  参考訳（メタデータ） (2020-02-12T18:59:18Z)

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

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