論文の概要: Complexity assessments for decidable fragments of Set Theory. III: A
quadratic reduction of constraints over nested sets to Boolean formulae
- arxiv url: http://arxiv.org/abs/2112.04797v1
- Date: Thu, 9 Dec 2021 09:36:39 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-10 15:26:39.876574
- Title: Complexity assessments for decidable fragments of Set Theory. III: A
quadratic reduction of constraints over nested sets to Boolean formulae
- Title（参考訳）: 集合論の決定可能な断片に対する複雑性評価
III: ブール公式へのネスト集合上の制約の二次的還元
- Authors: Domenico Cantone, Andrea De Domenico, Pietro Maugeri, Eugenio G.
Omodeo
- Abstract要約: 変換は、$x=ysetminus z$, $x neq ysetminus z$, $z =x$ という形のリテラルの結合からなる。
対象言語の式は、集合のブール環にまたがる変数と、等式、非可分性、包含性を指定する差分演算子とレギュレータを含む。
提案した翻訳は2次アルゴリズムの時間複雑度を持ち、どちらもNP完全満足度問題を持つことが知られている2つの言語を橋渡しする。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: As a contribution to quantitative set-theoretic inferencing, a translation is
proposed of conjunctions of literals of the forms $x=y\setminus z$, $x \neq
y\setminus z$, and $z =\{x\}$, where $x,y,z$ stand for variables ranging over
the von Neumann universe of sets, into unquantified Boolean formulae of a
rather simple conjunctive normal form. The formulae in the target language
involve variables ranging over a Boolean ring of sets, along with a difference
operator and relators designating equality, non-disjointness and inclusion.
Moreover, the result of each translation is a conjunction of literals of the
forms $x=y\setminus z$, $x\neq y\setminus z$ and of implications whose
antecedents are isolated literals and whose consequents are either inclusions
(strict or non-strict) between variables, or equalities between variables.
Besides reflecting a simple and natural semantics, which ensures
satisfiability-preservation, the proposed translation has quadratic algorithmic
time-complexity, and bridges two languages both of which are known to have an
NP-complete satisfiability problem.
- Abstract（参考訳）: 量的集合論的な推論への寄与として、$x=y\setminus z$, $x \neq y\setminus z$, and $z =\{x\}$, ここで$x,y,z$ は集合のフォン・ノイマン宇宙上の変数に対して、比較的単純な連結正規形式のブール式を不定式化したものである。
対象言語の式は、集合のブール環にまたがる変数と、等式、非可分性、包含性を指定する差分演算子とレギュレータを含む。
さらに、各翻訳の結果は、$x=y\setminus z$, $x\neq y\setminus z$という形式のリテラルと、先行項が孤立リテラルで変数間の包含(限定的または非限定的)か変数間の等式である含意の結合である。
満足度保存を保証する単純で自然なセマンティクスを反映するだけでなく、提案した翻訳は2次アルゴリズムの時間複雑度を持ち、どちらもNP完全満足度問題で知られている2つの言語を橋渡しする。
関連論文リスト
- The Sample Complexity of Simple Binary Hypothesis Testing [7.127829790714167]
単純な二項仮説テストのサンプルの複雑さは、いずれの設定でも$p$と$q$の2つの分布を区別するのに必要となる最小のi.d.サンプルである。
この問題は、$alpha = beta$ (prior-free) または $alpha = 1/2$ (Bayesian) でのみ研究されている。
論文 参考訳（メタデータ） (2024-03-25T17:42:32Z) - Complexity-Theoretic Implications of Multicalibration [6.967392207053045]
多精度予測器はより強い条件を満たす:それらはコレクションの各セットで校正される。
この複雑性理論的正則性レンマは、異なる領域に影響を及ぼすことが知られている。
すべての函数(その硬さによらず)が不随伴なハードコア集合の小さな集合を持つことが示される。
論文 参考訳（メタデータ） (2023-12-28T18:53:21Z) - Decomposing Hard SAT Instances with Metaheuristic Optimization [52.03315747221343]
分解硬度(d硬度)の概念を導入する。
d-硬度が$C$ w.r.tの硬度の推定値を示すことを示す。
論文 参考訳（メタデータ） (2023-12-16T12:44:36Z) - Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions [18.086061048484616]
平衡問題の幅広いクラスをモデル化した有限サム単調包含問題について検討する。
我々の主な貢献は、複雑性の保証を改善するために分散還元を利用する古典的ハルパーン反復の変種である。
我々は、この複雑さが単調なリプシッツ設定では改善できないと論じる。
論文 参考訳（メタデータ） (2023-10-04T17:24:45Z) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [56.457634640638254]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳（メタデータ） (2023-10-02T08:15:52Z) - (1+1) Genetic Programming With Functionally Complete Instruction Sets
Can Evolve Boolean Conjunctions and Disjunctions with Arbitrarily Small Error [16.075339182916128]
GPシステムは、必要最小限のコンポーネントが備わっている場合、$n$変数の結合を進化させることができる。
GPシステムは、$O(ell n log2 n)$, $ell geq が受理木の大きさの極限であるような予想において、正確なターゲット関数を進化させることができることを示す。
論文 参考訳（メタデータ） (2023-03-13T20:24:21Z) - Learning Algebraic Recombination for Compositional Generalization [71.78771157219428]
合成一般化のための代数的組換え学習のためのエンドツーエンドニューラルモデルLeARを提案する。
主要な洞察は、意味解析タスクを潜在構文代数学と意味代数学の間の準同型としてモデル化することである。
2つの現実的・包括的構成一般化の実験は、我々のモデルの有効性を実証している。
論文 参考訳（メタデータ） (2021-07-14T07:23:46Z) - Efficient Explanations With Relevant Sets [30.296628060841645]
本稿では,$delta$-relevant 集合の実用的限界に対処するための解について検討する。
$delta$-relevant 集合の部分集合の計算は NP であり、NP のオラクルへの多くの呼び出しで解ける。
論文 参考訳（メタデータ） (2021-06-01T14:57:58Z) - Sub-bosonic (deformed) ladder operators [62.997667081978825]
ファジィネスという厳密な概念から派生した変形生成および消滅作用素のクラスを提示する。
これにより変形し、ボゾン準可換関係は、修正された退化エネルギーとフォック状態を持つ単純な代数構造を誘導する。
さらに、量子論において導入された形式論がもたらす可能性について、例えば、自由準ボソンの分散関係における線型性からの偏差について検討する。
論文 参考訳（メタデータ） (2020-09-10T20:53:58Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳（メタデータ） (2020-07-07T09:00:57Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。