論文の概要: The Horn Non-Clausal Class and its Polynomiality
- arxiv url: http://arxiv.org/abs/2108.13744v1
- Date: Tue, 31 Aug 2021 10:55:19 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-01 22:08:27.687479
- Title: The Horn Non-Clausal Class and its Polynomiality
- Title（参考訳）: ホーン非閉クラスとその多項式性
- Authors: Gonzalo E. Imaz
- Abstract要約: 命題非クラス式(NC)の表現性は、クラス式よりも指数関数的にリッチである。
ホルン非クラウサル式 (HornNC) のハイブリッドクラス $mathbbH_NC$ を定義する。
我々は$mathbbH_NC$が線型認識可能であることを証明し、Hornクラスよりも厳密かつ指数的にリッチであることも証明する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The expressiveness of propositional non-clausal (NC) formulas is
exponentially richer than that of clausal formulas. Yet, clausal efficiency
outperforms non-clausal one. Indeed, a major weakness of the latter is that,
while Horn clausal formulas, along with Horn algorithms, are crucial for the
high efficiency of clausal reasoning, no Horn-like formulas in non-clausal form
had been proposed. To overcome such weakness, we define the hybrid class
$\mathbb{H_{NC}}$ of Horn Non-Clausal (Horn-NC) formulas, by adequately lifting
the Horn pattern to NC form, and argue that $\mathbb{H_{NC}}$, along with
future Horn-NC algorithms, shall increase non-clausal efficiency just as the
Horn class has increased clausal efficiency. Secondly, we: (i) give the
compact, inductive definition of $\mathbb{H_{NC}}$; (ii) prove that
syntactically $\mathbb{H_{NC}}$ subsumes the Horn class but semantically both
classes are equivalent, and (iii) characterize the non-clausal formulas
belonging to $\mathbb{H_{NC}}$. Thirdly, we define the Non-Clausal
Unit-Resolution calculus, $UR_{NC}$, and prove that it checks the
satisfiability of $\mathbb{H_{NC}}$ in polynomial time. This fact, to our
knowledge, makes $\mathbb{H_{NC}}$ the first characterized polynomial class in
NC reasoning. Finally, we prove that $\mathbb{H_{NC}}$ is linearly
recognizable, and also that it is both strictly succincter and exponentially
richer than the Horn class. We discuss that in NC automated reasoning, e.g.
satisfiability solving, theorem proving, logic programming, etc., can directly
benefit from $\mathbb{H_{NC}}$ and $UR_{NC}$ and that, as a by-product of its
proved properties, $\mathbb{H_{NC}}$ arises as a new alternative to analyze
Horn functions and implication systems.
- Abstract（参考訳）: 命題的非閉包式(nc)の表現性は閉包式よりも指数関数的に豊かである。
しかし、クローズ効率は非クローズ効率を上回っている。
実際、後者の大きな弱点は、ホーンクローサルの公式は、ホーンアルゴリズムとともに、クローサル推論の高効率化に不可欠であるが、非クラウサル形式のホーン様公式は提案されていないことである。
このような弱点を克服するため、Horn Non-Clausal (Horn-NC) の公式のハイブリッドクラス $\mathbb{H_{NC}}$ を NC 形式に適切に持ち上げ、将来のHorn-NC アルゴリズムとともに、Horn クラスが clausal efficiency を増大するのと同じように非クラス効率を向上すると主張する。
i) $\mathbb{H_{NC}}$; (ii) 構文的に$\mathbb{H_{NC}}$がホーン類を仮定することを示すが、意味的には両方のクラスは同値であり、(iii)$\mathbb{H_{NC}}$に属する非クラス式を特徴づける。
第三に、Non-Clausal Unit-Resolution calculusを$UR_{NC}$と定義し、多項式時間で$\mathbb{H_{NC}}$の満足度をチェックする。
この事実は、我々の知る限り、$\mathbb{H_{NC}}$ NC推論において初めて特徴づけられる多項式類となる。
最後に、$\mathbb{H_{NC}}$ が線型認識可能であることを証明し、ホーン類よりも厳密かつ指数的にリッチであることも証明する。
私たちはそれをnc自動推論で議論します。
満足度解決、定理証明、論理プログラミング等は、$\mathbb{H_{NC}}$と$UR_{NC}$から直接利益を得ることができ、証明された性質の副産物として、$\mathbb{H_{NC}}$はホーン関数や含意系を解析するための新しい代替品として現れる。
関連論文リスト
- A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Rigorous derivation of the Efimov effect in a simple model [68.8204255655161]
我々は、2体ゼロレンジ相互作用と、与えられた半径$a>0$の3体ハードコア反発を持つ$mathbbR3$の3つの同一ボソンの系を考える。
論文 参考訳（メタデータ） (2023-06-21T10:11:28Z) - Quantum and classical low-degree learning via a dimension-free Remez
inequality [52.12931955662553]
ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。
巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。
我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
論文 参考訳（メタデータ） (2023-01-04T04:15:40Z) - SQ Lower Bounds for Learning Single Neurons with Massart Noise [40.1662767099183]
マスアートノイズの存在下で単一ニューロンを学習するPAC。
我々は、任意の定数係数内で最適な誤差を近似できる効率的なSQアルゴリズムが存在しないことを証明した。
論文 参考訳（メタデータ） (2022-10-18T15:58:00Z) - Quantum teleportation in the commuting operator framework [63.69764116066747]
我々は、相対可換群 $N'cap M$ に対して、Nsubseteq M$ と tracial von Neumann algebra の大きいクラスに対する非バイアス付きテレポーテーションスキームを提示する。
N$ に対する厳密なテレポーテーションスキームは、必ずしも正則ユニタリな Pimsner-Popa 基底 $M_n(mathbbC)$ over$N'$ から生じる。
論文 参考訳（メタデータ） (2022-08-02T00:20:46Z) - Some Remarks on the Regularized Hamiltonian for Three Bosons with
Contact Interactions [77.34726150561087]
3次元のゼロレンジ力を介して相互作用する3つのボソン系のモデルハミルトンの性質について論じる。
特に、適当な二次形式 $Q$ から始め、自己随伴およびハミルトンの$mathcal H$ の下から有界となるものを構築することができる。
しきい値 $gamma_c$ が最適であることは、次の2次形式 $Q$ が下から非有界であるという意味では、$gamma_c$ が最適であることを示している。
論文 参考訳（メタデータ） (2022-07-01T10:01:14Z) - The Possibilistic Horn Non-Clausal Knowledge Bases [0.0]
可能性論理(Posibilistic logic)は、不確実かつ部分的に矛盾した情報を扱うための最も拡張されたアプローチである。
元のNC形式で公式を計算することで、確率的非クラス推論における顕著な進歩を示す。
論文 参考訳（メタデータ） (2021-11-15T10:18:49Z) - A First Polynomial Non-Clausal Class in Many-Valued Logic [0.0]
正規多値ホーン非クラウサル類(英: regular many-valued Horn Non-Clausal class、RH)は命題論理において最も効率的である。
正規非正則単位分解(RUR-NC)は命題論理において最も効率的である。
論文 参考訳（メタデータ） (2021-10-21T00:00:46Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z) - Novel methods to construct nonlocal sets of orthogonal product states in
arbitrary bipartite high-dimensional system [0.0]
我々は、$mathbbCd otimes mathbbCd$ for $dgeq3$における非局所積状態を構成する新しい一般手法を提案する。
それらの積状態の局所的不明瞭性を示す巧妙な証明を与える。
我々の研究は、局所的に区別できないOPSの構造と分類を理解するのに大いに役立ちます。
論文 参考訳（メタデータ） (2020-03-16T23:27:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。