Fugu-MT 論文翻訳(概要): Reducing SAT to Max2XOR

論文の概要: 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問題に対する新しい解決規則を提案する。

関連論文リスト

IGMaxHS -- An Incremental MaxSAT Solver with Support for XOR Clauses [0.0]
IGMaxHS は iMaxHS と GaussMaxHS をベースとしているが, XOR の制約は GaussMaxHS よりも少ない。 IGMaxHSは、不正な不満足な判断も、不正なモデルも、一貫性のないコストモデルの組み合わせも報告していない唯一の解決法である。 IGMaxHSは,ミュンヘン量子ツールキットを用いたシミュレーションにより,量子カラーコードを復号化可能であることを示す。
論文参考訳（メタデータ） (2024-10-21T11:21:21Z)
Resource-Constrained Heuristic for Max-SAT [0.848762374187855]
より大規模な問題をより小さなサブコンポーネントに繰り返し分解する,Max-SATのインスタンスに対するリソース制約を提案する。本研究では,所定のSATインスタンスの構造を利用するグラフベースの新しい手法を含む,変数選択手法の集合を分析する。我々は,Max-SAT評価ベンチマークを用いて,ランダムに生成されたMax-SATインスタンスと実世界の実例について実験を行った。
論文参考訳（メタデータ） (2024-10-11T18:20:08Z)
Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文参考訳（メタデータ） (2024-08-14T19:04:13Z)
SAT, Gadgets, Max2XOR, and Quantum Annealers [3.3885466945315246]
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)
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)
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)

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