Fugu-MT 論文翻訳(概要): Common equivalence and size after forgetting

論文の概要: Common equivalence and size after forgetting

arxiv url: http://arxiv.org/abs/2006.11152v2
Date: Thu, 6 May 2021 12:07:40 GMT
ステータス: 処理完了
システム内更新日: 2022-11-19 05:07:19.274115
Title: Common equivalence and size after forgetting
Title（参考訳）: 忘れた後の共通同値と大きさ
Authors: Paolo Liberatore
Abstract要約: 命題式からの変数の取得は、そのサイズを増大させる可能性がある。新しい変数の導入は、それを短くする方法である。共通同値は、空間における共通同値を忘れたり、確認したりするという点で表すことができる。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Forgetting variables from a propositional formula may increase its size. Introducing new variables is a way to shorten it. Both operations can be expressed in terms of common equivalence, a weakened version of equivalence. In turn, common equivalence can be expressed in terms of forgetting. An algorithm for forgetting and checking common equivalence in polynomial space is given for the Horn case; it is polynomial-time for the subclass of single-head formulae. Minimizing after forgetting is polynomial-time if the formula is also acyclic and variables cannot be introduced, NP-hard when they can.
Abstract（参考訳）: 命題式からの変数の取得は、そのサイズを増大させる。新しい変数の導入は、それを短くする方法である。どちらの演算も、同値の弱化バージョンである共通同値の観点から表現することができる。逆に、共通の同値性は忘れるという観点で表現できる。多項式空間における共通同値性を忘れるアルゴリズムは、ホーンケースに対して与えられ、それは単頭式の部分クラスに対する多項式時間である。忘れた後の最小化は多項式時間であり、式が非巡回であり、変数を導入できない場合、NPハードである。

関連論文リスト

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)
Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
論文参考訳（メタデータ） (2023-10-05T07:10:40Z)
A Direct Reduction from the Polynomial to the Adversary Method [92.54311953850168]
逆法に(双対の形で)方法から単純かつ直接的に還元する。これは、双対形式におけるどんな下界も、特定の形式の逆下界であることを示している。
論文参考訳（メタデータ） (2023-01-24T21:37:20Z)
An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。アルファベットのサイズについては、定値対分離の複雑さがある。
論文参考訳（メタデータ） (2023-01-22T22:08:28Z)
Superredundancy: A tool for Boolean formula minimization complexity analysis [0.0]
超冗長節 (superredundant clause) は、公式の解法閉鎖において冗長な節である。逆の超冗長性の概念は、与えられたものと同値であるすべての最小のCNF式における節のメンバシップを保証する。
論文参考訳（メタデータ） (2022-05-02T09:17:52Z)
Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
量子計算の2つのモデル: CQ_dとQC_d。 CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。 CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
論文参考訳（メタデータ） (2022-01-06T03:10:53Z)
Computing the quantum guesswork: a quadratic assignment problem [6.445605125467573]
従来の計算手法は、半定値の標準的なプログラミング技術に基づいていた。確率分布が均一な量子ビットアンサンブルの量子推定処理を計算すれば、よりクワッドラティックなスピードアップがもたらされることを示す。例として、正則および準正則なクォービット状態集合の推理を計算する。
論文参考訳（メタデータ） (2021-12-03T01:24:57Z)
A Reinforcement Learning Environment for Polyhedral Optimizations [68.8204255655161]
マルコフ決定過程(MDP)として多面体モデルにおける法的変換空間の形状に依存しない定式化を提案する。変換を使う代わりに、定式化は可能なスケジュールの抽象空間に基づいている。我々の総合的MDP定式化は、強化学習を用いて幅広いループで最適化ポリシーを学習することを可能にする。
論文参考訳（メタデータ） (2021-04-28T12:41:52Z)
One head is better than two: a polynomial restriction for propositional definite Horn forgetting [0.0]
忘れることは、命題ホルンの公式の単純な場合でさえ np-完全である。いくつかの公式はシングルヘッドではなく、忘れるのを簡単にするために作成することができる。
論文参考訳（メタデータ） (2020-09-16T06:49:08Z)
The ghosts of forgotten things: A study on size after forgetting [0.0]
forttingは、他の変数の制約を保ちながら、論理式から変数を除去する。本稿では,このような増加の影響を論じ,その現象の計算的性質を解析する。
論文参考訳（メタデータ） (2020-05-08T15:56:01Z)
Bounds on the size of PC and URC formulas [0.0]
式が存在量化された補助変数を使って関数を表す場合、それは関数の符号化と呼ばれる。我々はPC と URC の公式とエンコーディングのサイズについていくつかの結果を示した。任意のq-Horn式に対して、補助変数を用いて同じ関数を符号化する大きさのURCを示す。
論文参考訳（メタデータ） (2020-01-03T13:15:32Z)

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