論文の概要: Bridging Weighted First Order Model Counting and Graph Polynomials
- arxiv url: http://arxiv.org/abs/2407.11877v1
- Date: Tue, 16 Jul 2024 16:01:25 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-17 14:03:36.666949
- Title: Bridging Weighted First Order Model Counting and Graph Polynomials
- Title（参考訳）: ブリッジ重み付き1次モデルカウントとグラフ多項式
- Authors: Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, Yuyi Wang,
- Abstract要約: 重み付き一階述語モデルカウント問題(WFOMC)は、与えられた一階述語論理文のモデルの重み付き和を計算することを要求する。
Weak Connectedness Polynomials and Strong Connectedness Polynomials for first-order logic sentences。
- 参考スコア（独自算出の注目度）: 6.2686964302152735
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Weighted First-Order Model Counting Problem (WFOMC) asks to compute the weighted sum of models of a given first-order logic sentence over a given domain. It can be solved in time polynomial in the domain size for sentences from the two-variable fragment with counting quantifiers, known as $C^2$. This polynomial-time complexity is also retained when extending $C^2$ by one of the following axioms: linear order axiom, tree axiom, forest axiom, directed acyclic graph axiom or connectedness axiom. An interesting question remains as to which other axioms can be added to the first-order sentences in this way. We provide a new perspective on this problem by associating WFOMC with graph polynomials. Using WFOMC, we define Weak Connectedness Polynomial and Strong Connectedness Polynomials for first-order logic sentences. It turns out that these polynomials have the following interesting properties. First, they can be computed in polynomial time in the domain size for sentences from $C^2$. Second, we can use them to solve WFOMC with all of the existing axioms known to be tractable as well as with new ones such as bipartiteness, strong connectedness, being a spanning subgraph, having $k$ connected components, etc. Third, the well-known Tutte polynomial can be recovered as a special case of the Weak Connectedness Polynomial, and the Strict and Non-Strict Directed Chromatic Polynomials can be recovered from the Strong Connectedness Polynomials, which allows us to show that these important graph polynomials can be computed in time polynomial in the number of vertices for any graph that can be encoded by a fixed $C^2$ sentence and a conjunction of an arbitrary number of ground unary literals.
- Abstract（参考訳）: 重み付き一階述語モデルカウント問題(WFOMC)は、与えられた一階述語論理文のモデルの重み付き和を与えられたドメイン上で計算することを要求する。
C^2$ と呼ばれる数量化子を持つ2変数の断片からの文のドメインサイズの時間多項式で解くことができる。
この多項式時間の複雑性は、線形順序公理、木公理、森林公理、有向非巡回グラフ公理または連結性公理の1つによって$C^2$を拡張するときにも維持される。
興味深い疑問は、このような一階述語に他の公理を加えることができるかという点である。
グラフ多項式とWFOMCを関連付けることにより,この問題に対する新たな視点を提供する。
Weak Connectedness PolynomialsとStrong Connectedness Polynomialsを一階述語論理文に対して定義する。
これらの多項式は以下の興味深い性質を持つ。
まず、C^2$の文に対して、ドメインサイズの多項式時間で計算できる。
第二に、WFOMCを既存の公理の全てと、二分性、強い接続性、スパンニング部分グラフ、$k$接続されたコンポーネントなどの新しいもので解くことができる。
第三に、よく知られたトゥッテ多項式は弱連結性多項式の特別な場合として復元することができ、Strict and Non-Strict Directed Chromatic Polynomials は強連結性多項式から復元することができ、固定された$C^2$文でエンコードできるグラフの頂点数と任意の基底ユニタリリテラルの結合でこれらの重要なグラフ多項式が時間多項式で計算可能であることを示すことができる。
関連論文リスト
- On Maximal Families of Binary Polynomials with Pairwise Linear Common Factors [1.249418440326334]
二進体 $mathbbF$ 上の極大族を特徴づける。
我々の発見は、よりオープンないくつかの質問を呼び起こし、この研究の拡張バージョンで対処する予定です。
論文 参考訳（メタデータ） (2024-05-14T16:30:28Z) - Lifted Inference beyond First-Order Logic [8.577974472273256]
関係性の一つが有向非巡回グラフ、連結グラフ、木、森である場合、mathrmC2$文はドメインリフト可能であることを示す。
我々の結果は「分割による数え方」という新奇で一般的な方法論に頼っている。
論文 参考訳（メタデータ） (2023-08-22T18:58:21Z) - Weighted First Order Model Counting with Directed Acyclic Graph Axioms [7.766921168069532]
多くのSRLにおける確率的推論と学習は、重み付き第一モデルカウント(WFOMC)に還元できる
WFOMCは難解であることが知られている(mathrm#P$ complete)。
我々は,DAG(Directed Acyclic Graph)を除外したフラグメント$mathrmC2$,すなわち公理DAGを表す公理化グラフがドメインリフト可能であることを示す。
論文 参考訳（メタデータ） (2023-02-20T08:35:13Z) - 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) - 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) - Lifted Inference with Linear Order Axiom [0.0]
We consider the task of weighted first-order model counting (WFOMC)
我々は、少なくとも2つの論理変数を持つ論理文の WFOMC が $n$ の時間で実行可能であることを示す。
線形順序でWFOMCをn$で計算できる新しい動的プログラミングベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-11-02T14:38:01Z) - Bilinear Classes: A Structural Framework for Provable Generalization in
RL [119.42509700822484]
Bilinear Classesは強化学習の一般化を可能にする新しい構造フレームワークである。
このフレームワークは、サンプルの複雑さが達成可能な、ほとんどすべての既存のモデルを取り込んでいる。
我々の主な成果は、双線形クラスのためのサンプル複雑性を持つRLアルゴリズムである。
論文 参考訳（メタデータ） (2021-03-19T16:34:20Z) - Finite-Function-Encoding Quantum States [52.77024349608834]
任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。
それらの構造的特性について検討する。
論文 参考訳（メタデータ） (2020-12-01T13:53:23Z) - Weighted Model Counting in the two variable fragment with Cardinality
Constraints: A Closed Form Formula [7.766921168069532]
重み付き一階モデルカウント(WFOMC)は、与えられた有限領域上の一階理論のモデルの重み付き和を計算する。
WFOMCの推論を定式化するためのツールとして,リフト解釈の概念を導入する。
次に、この閉形式を拡張して、存在量化器と濃度制約をドメインリフト性を失うことなく組み込む。
論文 参考訳（メタデータ） (2020-09-25T13:50:18Z) - SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。
実験では最先端のアルゴリズムよりも優れています。
論文 参考訳（メタデータ） (2020-02-22T01:03:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。