論文の概要: Reducing SAT to Max2XOR
- arxiv url: http://arxiv.org/abs/2204.01774v1
- Date: Mon, 4 Apr 2022 18:06:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-07 01:03:12.668306
- Title: Reducing SAT to Max2XOR
- Title(参考訳): SAT を Max2XOR に還元する
- Authors: Carlos Ans\'otegui, Jordi Levy
- Abstract要約: SAT節をMax2XOR制約に変換するためのガジェットを提案する。
また、Max2XOR問題に対する新しい解決規則も提示する。
- 参考スコア(独自算出の注目度): 4.264192013842096
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Representing some problems with XOR clauses (parity constraints) can allow to
apply more efficient reasoning techniques. In this paper, we present a gadget
for translating SAT clauses into Max2XOR constraints, i.e., XOR clauses of at
most 2 variables equal to zero or to one. Additionally, we present new
resolution rules for the Max2XOR problem which asks for which is the maximum
number of constraints that can be satisfied from a set of 2XOR equations.
- Abstract(参考訳): XOR節(パリティ制約)で問題を表現することで、より効率的な推論技術を適用することができる。
本稿では,SAT 節を Max2XOR 制約,すなわち少なくとも 2 変数の XOR 節を 0 または 1 に翻訳するガジェットを提案する。
さらに,一組の2XOR方程式から満たされる制約の最大数を求めるMax2XOR問題に対する新しい解決規則を提案する。
関連論文リスト
- SAT, Gadgets, Max2XOR, and Quantum Annealers [2.0450716801079443]
SATをMax2XORに還元するガジェットをいくつか提示する。
SATインスタンスを量子アニールの初期構成に変換する方法を示す。
論文 参考訳(メタデータ) (2024-02-29T23:18:45Z) - Qubit Number Optimization for Restriction Terms of QUBO Hamiltonians [62.997667081978825]
数学的には$R$の分数値を求めることができる。
制限ハミルトニアンの実装に必要な量子ビット数をさらに減らす方法を示す。
最後に、FRCの実装に直面した場合、DWaveのAdvantage$_$system4.1 Quantum Annealer(QA)の応答を特徴付ける。
論文 参考訳(メタデータ) (2023-06-12T08:25:56Z) - UpMax: User partitioning for MaxSAT [2.2022484178680872]
パーティショニングは、不満に基づくMaxSATアルゴリズムのパフォーマンスに大きな影響を与える。
本稿では,分割処理をMaxSATの解法から切り離すUpMaxという新しいフレームワークを提案する。
論文 参考訳(メタデータ) (2023-05-25T15:50:00Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳(メタデータ) (2022-11-16T18:59:54Z) - DPMS: An ADD-Based Symbolic Approach for Generalized MaxSAT Solving [45.21499915442282]
本稿では,ハイブリッド制約を用いた一般化MaxSAT問題の解法について,新しい動的プログラミング手法を提案する。
我々の汎用フレームワークは、MaxSAT、Min-MaxSAT、MinSATといったCNF-MaxSATの多くの一般化をハイブリッド制約で認めている。
実験の結果、DPMSは様々な手法に基づく他のアルゴリズムがすべて失敗し、特定の問題を迅速に解決できることがわかった。
論文 参考訳(メタデータ) (2022-05-08T00:31:53Z) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。
我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。
我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
論文 参考訳(メタデータ) (2022-03-11T17:19:26Z) - Transformer-based Machine Learning for Fast SAT Solvers and Logic
Synthesis [63.53283025435107]
CNFベースのSATとMaxSATは論理合成と検証システムの中心である。
そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
論文 参考訳(メタデータ) (2021-07-15T04:47:35Z) - Incomplete MaxSAT Approaches for Combinatorial Testing [0.0]
本稿では,最小長の制約付き混合被覆アレイを構築するためのSAT(Satifiability)に基づくアプローチを提案する。
この問題はシステム障害検出のためのコンビネータテストの中心である。
論文 参考訳(メタデータ) (2021-05-26T14:00:56Z) - From Checking to Inference: Actual Causality Computations as
Optimization Problems [79.87179017975235]
本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。
8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
論文 参考訳(メタデータ) (2020-06-05T10:56:52Z) - Encoding Linear Constraints into SAT [0.0]
複数値決定ダイアグラムとソートネットワークに基づく新しいSATエンコーディングを定義する。
線形整数解法 (MIP) よりも優れており, 適切な問題に対して LCG や SMT より優れている場合もある。
論文 参考訳(メタデータ) (2020-05-05T11:37:43Z) - Determining the Multiplicative Complexity of Boolean Functions using SAT [1.4902915966744057]
ブール関数の乗法的複雑性を決定するための構築的SATアルゴリズムを提案する。
提案アルゴリズムは,全5入力アフィン等価クラスの代表に対して最適XAGを求めることができる。
論文 参考訳(メタデータ) (2020-05-04T18:29:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。