Fugu-MT 論文翻訳(概要): On the size of irredundant propagation complete CNF formulas

論文の概要: On the size of irredundant propagation complete CNF formulas

arxiv url: http://arxiv.org/abs/2309.01750v1
Date: Mon, 4 Sep 2023 18:15:34 GMT
ステータス: 処理完了
システム内更新日: 2023-09-06 17:42:16.937934
Title: On the size of irredundant propagation complete CNF formulas
Title（参考訳）: 非冗長伝播完全cnf公式の大きさについて
Authors: Petr Savick\'y
Abstract要約: 我々は、$n$変数の対称定値ホーン関数の伝搬完全(PC)CNF式について検討する。我々は、同じ関数に対する最小のPC式よりも小さいサイズが、$Omega(n/ln n)$ の既約PC式を示す。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We investigate propagation complete (PC) CNF formulas for a symmetric definite Horn function of $n$ variables and demonstrate that the minimum size of these formulas is closely related to specific covering numbers, namely, to the smallest number of $k$-subsets of an $n$-set covering all $(k-1)$-subsets for a suitable $k$. As a consequence, we demonstrate an irredundant PC formula whose size is larger than the size of a smallest PC formula for the same function by a factor $\Omega(n/\ln n)$. This complements a known polynomial upper bound on this factor.
Abstract（参考訳）: 我々は、$n$変数の対称定値ホーン関数の伝搬完全(PC) CNF式を調査し、これらの式の最小サイズが特定の被覆数、すなわち、適当な$k$に対するすべての$(k-1)$-subsetをカバーする$n$-subsetの最小数の$k$-subsetと密接に関連していることを示す。結果として、同じ関数に対する最小のPC式のサイズよりも、$\Omega(n/\ln n)$でサイズが大きくなる無矛盾なPC式を実演する。これはこの因子上の既知の多項式上界を補完する。

関連論文リスト

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)

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