論文の概要: On CNF formulas irredundant with respect to unit clause propagation

• arxiv url: http://arxiv.org/abs/2309.01750v4
• Date: Sun, 4 Aug 2024 12:52:05 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-07 00:25:32.774740
• Title: On CNF formulas irredundant with respect to unit clause propagation
• Title（参考訳）: 単位節の伝搬に無関係なCNF式について
• Authors: Petr Savický,
• Abstract要約: 2つのCNF式はucp-等価(ucp-equivalent)と呼ばれ、単位節の伝搬(UCP)に関して同じように振る舞う。 公式がucp-irredundant(英語版)と呼ばれるのは、任意の節を削除すると、元の句と等価でない公式が導かれるからである。
• 参考スコア（独自算出の注目度）: 1.9580473532948401
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Two CNF formulas are called ucp-equivalent, if they behave in the same way with respect to the unit clause propagation (UCP). A formula is called ucp-irredundant, if removing any clause leads to a formula which is not ucp-equivalent to the original one. As a consequence of known results, the ratio of the size of a ucp-irredundant formula and the size of a smallest ucp-equivalent formula is at most $n^2$, where $n$ is the number of the variables. We demonstrate an example of a ucp-irredundant formula for a symmetric definite Horn function which is larger than a smallest ucp-equivalent formula by a factor $\Omega(n/\ln n)$ and, hence, a general upper bound on the above ratio cannot be smaller than this.
• Abstract（参考訳）: 2つのCNF式はucp-等価(ucp-equivalent)と呼ばれ、単位節の伝搬(UCP)に関して同じように振る舞う。 公式がucp-irredundant(英語版)と呼ばれるのは、任意の節を削除すると、元の句と等価でない公式が導かれるからである。 既知の結果の結果、ucp-不等式のサイズと最小のucp-等価式のサイズの比率は、少なくとも$n^2$であり、$n$は変数の数である。 対称定値ホーン関数に対するucp-不等式の例を、$\Omega(n/\ln n)$ で最小のucp-等価式より大きくし、したがって上記の比の一般上界は、これより小さくならない。

関連論文リスト

• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。 1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。 テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
  論文  参考訳（メタデータ） (2022-11-10T00:40:37Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。 既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。 本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
  論文  参考訳（メタデータ） (2022-10-08T08:26:22Z)
• 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)
• Superredundancy: A tool for Boolean formula minimization complexity analysis [0.0]
  超冗長節 (superredundant clause) は、公式の解法閉鎖において冗長な節である。 逆の超冗長性の概念は、与えられたものと同値であるすべての最小のCNF式における節のメンバシップを保証する。
  論文  参考訳（メタデータ） (2022-05-02T09:17:52Z)
• A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs [4.023424709659175]
  制約あたり$k$変数(k-CSP)によるランダム制約満足度問題の強い反響を証明する。 割当数$p$の制約で満たされたランダムk-CSPインスタンスの場合、最適値が最大値$p+O_k(epsilon)$の制約で満足する証明書を効率的に計算できる。
  論文  参考訳（メタデータ） (2022-04-20T16:21:21Z)
• Annihilating Entanglement Between Cones [77.34726150561087]
  ローレンツ錐体は、ある種の強いレジリエンス特性を満たす対称基底を持つ唯一の円錐体であることを示す。 我々の証明はローレンツ・コーンの対称性を利用しており、エンタングルメント蒸留のプロトコルに類似した2つの構造を適用している。
  論文  参考訳（メタデータ） (2021-10-22T15:02:39Z)
• 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)
• On the Modularity of Hypernetworks [103.1147622394852]
  構造化対象関数の場合、ハイパーネットワークにおけるトレーニング可能なパラメータの総数は、標準ニューラルネットワークのトレーニング可能なパラメータの数や埋め込み法よりも桁違いに小さいことを示す。
  論文  参考訳（メタデータ） (2020-02-23T22:51:52Z)
• Bounds on the size of PC and URC formulas [0.0]
  式が存在量化された補助変数を使って関数を表す場合、それは関数の符号化と呼ばれる。 我々はPC と URC の公式とエンコーディングのサイズについていくつかの結果を示した。 任意のq-Horn式に対して、補助変数を用いて同じ関数を符号化する大きさのURCを示す。
  論文  参考訳（メタデータ） (2020-01-03T13:15:32Z)

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

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