Fugu-MT 論文翻訳(概要): The ghosts of forgotten things: A study on size after forgetting

論文の概要: The ghosts of forgotten things: A study on size after forgetting

arxiv url: http://arxiv.org/abs/2005.04123v3
Date: Tue, 3 May 2022 06:54:52 GMT
ステータス: 処理完了
システム内更新日: 2022-12-05 13:10:11.377681
Title: The ghosts of forgotten things: A study on size after forgetting
Title（参考訳）: 忘れられた物の幽霊:忘れ去られた後の大きさの研究
Authors: Paolo Liberatore
Abstract要約: forttingは、他の変数の制約を保ちながら、論理式から変数を除去する。本稿では,このような増加の影響を論じ,その現象の計算的性質を解析する。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Forgetting is removing variables from a logical formula while preserving the constraints on the other variables. In spite of being a form of reduction, it does not always decrease the size of the formula and may sometimes increase it. This article discusses the implications of such an increase and analyzes the computational properties of the phenomenon. Given a propositional Horn formula, a set of variables and a maximum allowed size, deciding whether forgetting the variables from the formula can be expressed in that size is $D^p$-hard in $\Sigma^p_2$. The same problem for unrestricted propositional formulae is $D^p_2$-hard in $\Sigma^p_3$.
Abstract（参考訳）: forttingは、他の変数の制約を保ちながら、論理式から変数を除去する。還元の形式であるにもかかわらず、必ずしも公式のサイズを減少させるわけではなく、時には増加させることもある。本稿では,このような増加の影響を論じ,その現象の計算的性質を分析する。命題のホルン公式、変数の集合、最大許容サイズが与えられたとき、そのサイズで式から変数を忘れることは$D^p$-hard in $\Sigma^p_2$である。非制限命題公式の同じ問題は$D^p_2$-hard in $\Sigma^p_3$である。

関連論文リスト

Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文参考訳（メタデータ） (2024-11-01T17:59:53Z)
Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文参考訳（メタデータ） (2024-06-25T06:07:20Z)
Effective Minkowski Dimension of Deep Nonparametric Regression: Function Approximation and Statistical Theories [70.90012822736988]
ディープ非パラメトリック回帰に関する既存の理論は、入力データが低次元多様体上にある場合、ディープニューラルネットワークは本質的なデータ構造に適応できることを示した。本稿では,$mathcalS$で表される$mathbbRd$のサブセットに入力データが集中するという緩和された仮定を導入する。
論文参考訳（メタデータ） (2023-06-26T17:13:31Z)
Variance-aware robust reinforcement learning with linear function approximation with heavy-tailed rewards [6.932056534450556]
AdaOFUL と VARA という2つのアルゴリズムを,重み付き報酬の存在下でのオンラインシーケンシャルな意思決定のために提案する。 AdaOFULは、$widetildemathcalObigの最先端の後悔境界を達成する。 VarA は $widetildemathcalO(dsqrtHmathcalG*K)$ のより厳密な分散を考慮した後悔境界を達成する。
論文参考訳（メタデータ） (2023-03-09T22:16:28Z)
Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文参考訳（メタデータ） (2022-10-20T21:32:01Z)
Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文参考訳（メタデータ） (2022-05-23T17:59:18Z)
Superredundancy: A tool for Boolean formula minimization complexity analysis [0.0]
超冗長節 (superredundant clause) は、公式の解法閉鎖において冗長な節である。逆の超冗長性の概念は、与えられたものと同値であるすべての最小のCNF式における節のメンバシップを保証する。
論文参考訳（メタデータ） (2022-05-02T09:17:52Z)
Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文参考訳（メタデータ） (2021-01-29T18:57:52Z)
One head is better than two: a polynomial restriction for propositional definite Horn forgetting [0.0]
忘れることは、命題ホルンの公式の単純な場合でさえ np-完全である。いくつかの公式はシングルヘッドではなく、忘れるのを簡単にするために作成することができる。
論文参考訳（メタデータ） (2020-09-16T06:49:08Z)
Common equivalence and size after forgetting [0.0]
命題式からの変数の取得は、そのサイズを増大させる可能性がある。新しい変数の導入は、それを短くする方法である。共通同値は、空間における共通同値を忘れたり、確認したりするという点で表すことができる。
論文参考訳（メタデータ） (2020-06-19T14:27:51Z)

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