論文の概要: Tensor Network Rewriting Strategies for Satisfiability and Counting

• arxiv url: http://arxiv.org/abs/2004.06455v2
• Date: Mon, 6 Sep 2021 00:55:08 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-24 08:48:04.247540
• Title: Tensor Network Rewriting Strategies for Satisfiability and Counting
• Title（参考訳）: 満足度とカウントのためのテンソルネットワーク書き換え戦略
• Authors: Niel de Beaudrap (Quantum Group, Department of Computer Science, University of Oxford), Aleks Kissinger (Quantum Group, Department of Computer Science, University of Oxford), Konstantinos Meichanetzidis (Quantum Group, Department of Computer Science, University of Oxford and Cambridge Quantum Computing)
• Abstract要約: #SATのインスタンスは、標準的な方法でテンソルネットワークとして表現できる。 3SAT や #P-complete のようなNP完全であることが知られているクラス、例えば #2SAT では、対応する書き換え規則がダイアグラムにハイパーエッジを導入している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We provide a graphical treatment of SAT and #SAT on equal footing. Instances of #SAT can be represented as tensor networks in a standard way. These tensor networks are interpreted by diagrams of the ZH-calculus: a system to reason about tensors over C in terms of diagrams built from simple generators, in which computation may be carried out by transformations of diagrams alone. In general, nodes of ZH diagrams take parameters over C which determine the tensor coefficients; for the standard representation of #SAT instances, the coefficients take the value 0 or 1. Then, by choosing the coefficients of a diagram to range over B, we represent the corresponding instance of SAT. Thus, by interpreting a diagram either over the boolean semiring or the complex numbers, we instantiate either the decision or counting version of the problem. We find that for classes known to be in P, such as 2SAT and #XORSAT, the existence of appropriate rewrite rules allows for efficient simplification of the diagram, producing the solution in polynomial time. In contrast, for classes known to be NP-complete, such as 3SAT, or #P-complete, such as #2SAT, the corresponding rewrite rules introduce hyperedges to the diagrams, in numbers which are not easily bounded above by a polynomial. This diagrammatic approach unifies the diagnosis of the complexity of CSPs and #CSPs and shows promise in aiding tensor network contraction-based algorithms.
• Abstract（参考訳）: 等足歩行におけるSATと#SATのグラフィカルな扱いについて述べる。 #SATのインスタンスは、標準的な方法でテンソルネットワークとして表現できる。 これらのテンソルネットワークは、ZH-計算のダイアグラムによって解釈される:単純なジェネレータから構築されたダイアグラムの観点からC上のテンソルを推論するシステムで、ダイアグラムの変換だけで計算を行うことができる。 一般に、ZHダイアグラムのノードは、テンソル係数を決定する C 上のパラメータを取る; #SAT インスタンスの標準表現では、係数は 0 または 1 の値を取る。 すると、図形の係数を B を超える範囲に選び、対応する SAT のインスタンスを表す。 したがって、ブール半環か複素数上のダイアグラムを解釈することにより、問題の決定か数え方のいずれかをインスタンス化する。 2SAT や #XORSAT のような P に含まれることが知られているクラスに対して、適切な書き換え規則の存在はダイアグラムの効率的な単純化を可能にし、多項式時間で解を生成する。 対照的に、3SAT や#2SAT のようなNP完全クラスや#P完全クラスでは、対応する書き換え規則は、上述の多項式によって簡単に境界づけられない数で、ダイアグラムにハイパーエッジを導入する。 このダイアグラム的アプローチは、CSPと#CSPの複雑さの診断を統一し、テンソルネットワークの収縮に基づくアルゴリズムを支援することの約束を示す。

関連論文リスト

• Scalable Graph Compressed Convolutions [68.85227170390864]
  ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。 グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
  論文  参考訳（メタデータ） (2024-07-26T03:14:13Z)
• Equivalence Classes of Quantum Error-Correcting Codes [49.436750507696225]
  量子過程に影響を与える固有のノイズに対処するために、量子誤り訂正符号(QECC)が必要である。 我々は、テンソルネットワークからなるZXダイアグラムと呼ばれる形式でQECCを表す。
  論文  参考訳（メタデータ） (2024-06-17T20:48:43Z)
• GraSS: Combining Graph Neural Networks with Expert Knowledge for SAT Solver Selection [45.222591894755105]
  インスタンスの3部グラフ表現に基づくSATソルバ自動選択のための新しいアプローチであるGraSSを提案する。 我々は、新しいノードの特徴設計のようなドメイン固有の決定でグラフ表現を豊かにします。 生の表現とドメイン固有の選択の組み合わせが実行時の改善につながることを実証する。
  論文  参考訳（メタデータ） (2024-05-17T18:00:50Z)
• Machine Learning for SAT: Restricted Heuristics and New Graph Representations [0.8870188183999854]
  SATは、自動スケジューリングを含む多くのアプリケーションにおいて、基本的なNP完全問題である。 大きなインスタンスを解決するためには、SATソルバは、例えばDPLLとCDCLソルバの分岐変数を選択するなど、ブールアンに依存する必要がある。 我々は、訓練されたMLモデルでいくつかの初期ステップを行い、古典的なランタイムに制御をリリースする戦略を提案する。
  論文  参考訳（メタデータ） (2023-07-18T10:46:28Z)
• One-step replica symmetry breaking in the language of tensor networks [0.913755431537592]
  我々は1段階のレプリカ対称性破断空洞法とテンソルネットワークの正確なマッピングを開発する。 この2つのスキームは補足的な数学的および数値的なツールボックスを備えており、芸術のそれぞれの状態を改善するために利用することができる。
  論文  参考訳（メタデータ） (2023-06-26T18:42:51Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  離散グラフオートエンコーダ(DGAE)という新しいフレームワークを導入する。 まず、置換同変オートエンコーダを用いてグラフを離散潜在ノード表現の集合に変換する。 2番目のステップでは、離散潜在表現の集合をソートし、特別に設計された自己回帰モデルを用いてそれらの分布を学習する。
  論文  参考訳（メタデータ） (2023-06-13T12:40:39Z)
• W2SAT: Learning to generate SAT instances from Weighted Literal Incidence Graphs [11.139131079925113]
  W2SATは、現実世界/産業インスタンスから固有の構造と特性を学ぶことによってSAT式を生成するフレームワークである。 Weighted Literal Incidence Graph (WLIG)と呼ばれる新しいSAT表現を導入する。 WLIGからSAT問題への復号化は、新しい丘登り最適化法で重なり合う斜角を見つけることをモデル化する。
  論文  参考訳（メタデータ） (2023-02-01T06:30:41Z)
• Estimating the hardness of SAT encodings for Logical Equivalence Checking of Boolean circuits [58.83758257568434]
  LEC インスタンスの SAT 符号化の硬さは SAT パーティショニングでは textitw.r. と推定できることを示す。 そこで本研究では, SAT符号化の難易度を精度良く推定できるパーティショニング法を提案する。
  論文  参考訳（メタデータ） (2022-10-04T09:19:13Z)
• DeepSAT: An EDA-Driven Learning Framework for SAT [9.111341161918375]
  We present DeepSAT, a novel-to-end learning framework for the Boolean satisfiability (SAT) problem。 DeepSATは最先端の学習ベースSATソリューションに対して,大幅な精度向上を実現している。
  論文  参考訳（メタデータ） (2022-05-27T03:20:42Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)

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

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