Fugu-MT 論文翻訳(概要): Superredundancy: A tool for Boolean formula minimization complexity analysis

論文の概要: Superredundancy: A tool for Boolean formula minimization complexity analysis

arxiv url: http://arxiv.org/abs/2205.00762v1
Date: Mon, 2 May 2022 09:17:52 GMT
ステータス: 処理完了
システム内更新日: 2022-05-03 16:02:27.896169
Title: Superredundancy: A tool for Boolean formula minimization complexity analysis
Title（参考訳）: 超冗長性:ブール式最小化複雑性解析のためのツール
Authors: Paolo Liberatore
Abstract要約: 超冗長節 (superredundant clause) は、公式の解法閉鎖において冗長な節である。逆の超冗長性の概念は、与えられたものと同値であるすべての最小のCNF式における節のメンバシップを保証する。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: A superredundant clause is a clause that is redundant in the resolution closure of a formula. The converse concept of superirredundancy ensures membership of the clause in all minimal CNF formulae that are equivalent to the given one. This allows for building formulae where some clauses are fixed when minimizing size. An example are proofs of complexity hardness of the problems of minimal formula size. Others are proofs of size when forgetting variables or revising a formula. Most clauses can be made superirredundant by splitting them over a new variable.
Abstract（参考訳）: 超冗長節 (superredundant clause) は公式の解法閉鎖において冗長な節である。逆の超冗長性の概念は、与えられたものと同値であるすべての最小のCNF式における節のメンバシップを保証する。これにより、サイズを最小化するときにいくつかの節が固定される式を構築することができる。例えば、最小公式サイズの問題の複雑性のハードネスの証明がある。変数を忘れたり、公式を修正したりする際のサイズ証明もある。ほとんどの節は、新しい変数に分割することで超不規則にすることができる。

関連論文リスト

Decomposing Hard SAT Instances with Metaheuristic Optimization [52.03315747221343]
分解硬度(d硬度)の概念を導入する。 d-硬度が$C$ w.r.tの硬度の推定値を示すことを示す。
論文参考訳（メタデータ） (2023-12-16T12:44:36Z)
Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
論文参考訳（メタデータ） (2023-10-05T07:10:40Z)
Short Boolean Formulas as Explanations in Practice [4.445953630612019]
我々は、説明すべき対象属性に対する誤差を最小限に抑える長さ k のブール式をとる。いずれの場合も、アンサーセットプログラミングにおけるエンコーディングを用いて、異なる長さの説明公式を計算する。我々は、過度な適合を避けるが、それでも合理的に正確であり、重要なことは人間の解釈可能であるという説明を得る。
論文参考訳（メタデータ） (2023-07-13T11:57:04Z)
Complexity-Based Prompting for Multi-Step Reasoning [72.0057198610614]
大規模言語モデルに対して,多段階推論を行うための課題について検討する。中心的な疑問は、どの推論例が最も効果的なプロンプトを作るかである。多段階推論のためのシンプルで効果的な例選択方式である複雑性ベースのプロンプトを提案する。
論文参考訳（メタデータ） (2022-10-03T05:33:27Z)
Are Hitting Formulas Hard for Resolution? [26.575053800551633]
打球公式の解の複雑さは、いわゆる既約打球公式に支配されていることを示す。最大14節のヒット式を列挙する効率的なアルゴリズムを実装した。
論文参考訳（メタデータ） (2022-06-30T12:13:26Z)
SeqZero: Few-shot Compositional Semantic Parsing with Sequential Prompts and Zero-shot Models [57.29358388475983]
近年の研究では、事前訓練された言語モデルと標準発話を併用する有望な結果が示されている。本稿では,SeqZeroという構文解析手法を提案する。特に、SeqZeroは、提案した制約付き再スケーリングを備えたアンサンブルによって、両方のモデルのメリットを明らかにします。
論文参考訳（メタデータ） (2022-05-15T21:13:15Z)
One head is better than two: a polynomial restriction for propositional definite Horn forgetting [0.0]
忘れることは、命題ホルンの公式の単純な場合でさえ np-完全である。いくつかの公式はシングルヘッドではなく、忘れるのを簡単にするために作成することができる。
論文参考訳（メタデータ） (2020-09-16T06:49:08Z)
Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
論文参考訳（メタデータ） (2020-08-12T08:52:50Z)
Common equivalence and size after forgetting [0.0]
命題式からの変数の取得は、そのサイズを増大させる可能性がある。新しい変数の導入は、それを短くする方法である。共通同値は、空間における共通同値を忘れたり、確認したりするという点で表すことができる。
論文参考訳（メタデータ） (2020-06-19T14:27:51Z)
Superposition for Lambda-Free Higher-Order Logic [62.997667081978825]
本稿では,意図的および拡張的クラス数$lambda$-free高階論理に対して,難解な完全重ね合わせ計算を導入する。計算は完全単調でなくてもよい項順でパラメタ化され、$lambda$フリーの高次語彙パスとKnuth-Bendixの順序を使うことができる。
論文参考訳（メタデータ） (2020-05-05T12:10:21Z)
Bounds on the size of PC and URC formulas [0.0]
式が存在量化された補助変数を使って関数を表す場合、それは関数の符号化と呼ばれる。我々はPC と URC の公式とエンコーディングのサイズについていくつかの結果を示した。任意のq-Horn式に対して、補助変数を用いて同じ関数を符号化する大きさのURCを示す。
論文参考訳（メタデータ） (2020-01-03T13:15:32Z)

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