論文の概要: One head is better than two: a polynomial restriction for propositional definite Horn forgetting

• arxiv url: http://arxiv.org/abs/2009.07497v3
• Date: Sun, 28 Jan 2024 12:17:24 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-31 20:14:17.440540
• Title: One head is better than two: a polynomial restriction for propositional definite Horn forgetting
• Title（参考訳）: 1つの頭部は2より優れている:命題決定ホーンの忘れに対する多項式制限
• Authors: Paolo Liberatore
• Abstract要約: 忘れることは、命題ホルンの公式の単純な場合でさえ np-完全である。 いくつかの公式はシングルヘッドではなく、忘れるのを簡単にするために作成することができる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Logical forgetting is \np-complete even in the simple case of propositional Horn formulae, and may exponentially increase their size. A way to forget is to replace each variable to forget with the body of each clause whose head is the variable. It takes polynomial time in the single-head case: each variable is at most the head of a clause. Some formulae are not single-head but can be made so to simplify forgetting. They are single-head equivalent. The first contribution of this article is the study of a semantical characterization of single-head equivalence. Two necessary conditions are given. They are sufficient when the formula is inequivalent: it makes two sets of variables equivalent only if they are also equivalent to their intersection. All acyclic formulae are inequivalent. The second contribution of this article is an incomplete algorithm for turning a formula single-head. In case of success, forgetting becomes possible in polynomial time and produces a polynomial-size formula, none of which is otherwise guaranteed. The algorithm is complete on inequivalent formulae.
• Abstract（参考訳）: 論理的忘れは、命題ホルンの公式の単純な場合でさえ \np-完全であり、そのサイズを指数関数的に増やすことができる。 忘れる方法は、それぞれの変数を頭が変数である各節の本体に置き換えることである。 単頭の場合では多項式時間を取る: 各変数は少なくとも節の先頭である。 いくつかの公式は単頭ではなく、忘れるのを簡単にするために作られる。 単頭等価である。 本稿の最初の貢献は、単頭同値の意味論的特徴の研究である。 必要な条件は2つある。 公式が不等式であれば十分であり、2つの変数の集合はそれらの交叉と等価である場合に限り同値となる。 すべての非環式は同値である。 この記事の第二の貢献は、式を単頭回すための不完全なアルゴリズムである。 成功した場合、多項式時間で忘れることは可能となり、多項式サイズの公式を生成するが、それ以外は保証されない。 アルゴリズムは不等式で完備である。

関連論文リスト

• 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)
• A polynomial quantum computing algorithm for solving the dualization problem [75.38606213726906]
  2つの単調素関数 $f:0,1n to 0,1$ と $g:0,1n to 0,1$ が与えられたとき、双対化問題は$g$が$f$の双対かどうかを決定することである。 本稿では,双対化問題の決定版を時間内に解く量子コンピューティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-08-28T18:12:54Z)
• Constructions of $k$-uniform states in heterogeneous systems [65.63939256159891]
  一般の$k$に対して、異種系において$k$-一様状態を構成するための2つの一般的な方法を提案する。 我々は、各サブシステムの局所次元が素数となるような多くの新しい$k$一様状態を生成することができる。
  論文  参考訳（メタデータ） (2023-05-22T06:58:16Z)
• A Direct Reduction from the Polynomial to the Adversary Method [92.54311953850168]
  逆法に(双対の形で)方法から単純かつ直接的に還元する。 これは、双対形式におけるどんな下界も、特定の形式の逆下界であることを示している。
  論文  参考訳（メタデータ） (2023-01-24T21:37:20Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• Towards Antisymmetric Neural Ansatz Separation [48.80300074254758]
  反対称関数の2つの基本モデル、すなわち $f(x_sigma(1), ldots, x_sigma(N)) の形の函数 $f$ の分離について研究する。 これらは量子化学の文脈で発生し、フェルミオン系の波動関数の基本的なモデリングツールである。
  論文  参考訳（メタデータ） (2022-08-05T16:35:24Z)
• Are Hitting Formulas Hard for Resolution? [26.575053800551633]
  打球公式の解の複雑さは、いわゆる既約打球公式に支配されていることを示す。 最大14節のヒット式を列挙する効率的なアルゴリズムを実装した。
  論文  参考訳（メタデータ） (2022-06-30T12:13:26Z)
• Superredundancy: A tool for Boolean formula minimization complexity analysis [0.0]
  超冗長節 (superredundant clause) は、公式の解法閉鎖において冗長な節である。 逆の超冗長性の概念は、与えられたものと同値であるすべての最小のCNF式における節のメンバシップを保証する。
  論文  参考訳（メタデータ） (2022-05-02T09:17:52Z)
• Reconstructing a single-head formula to facilitate logical forgetting [0.2538209532048866]
  可能であれば単頭式を作成するアルゴリズムを示す。 それは完了することによって前のものよりも改善します:それは常に与えられたものと同等の単頭式を見つけます。
  論文  参考訳（メタデータ） (2020-12-18T12:25:49Z)
• Common equivalence and size after forgetting [0.0]
  命題式からの変数の取得は、そのサイズを増大させる可能性がある。 新しい変数の導入は、それを短くする方法である。 共通同値は、空間における共通同値を忘れたり、確認したりするという点で表すことができる。
  論文  参考訳（メタデータ） (2020-06-19T14:27:51Z)
• The ghosts of forgotten things: A study on size after forgetting [0.0]
  forttingは、他の変数の制約を保ちながら、論理式から変数を除去する。 本稿では,このような増加の影響を論じ,その現象の計算的性質を解析する。
  論文  参考訳（メタデータ） (2020-05-08T15:56:01Z)

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

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