論文の概要: Efficient Solution of Boolean Satisfiability Problems with Digital
MemComputing
- arxiv url: http://arxiv.org/abs/2011.06551v1
- Date: Thu, 12 Nov 2020 18:13:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-26 07:18:17.982806
- Title: Efficient Solution of Boolean Satisfiability Problems with Digital
MemComputing
- Title（参考訳）: ディジタルメム計算によるブール満足度問題の効率的な解法
- Authors: S.R.B. Bearden, Y.R. Pei, M. Di Ventra
- Abstract要約: メモリアシスト物理系はSAT問題を連続的に効率的に解くことができることを示す。
シミュレーションの効率は、元の物理系の集合力学特性と関係している。
我々は、物理学に着想を得た計算パラダイムの研究の方向性を広げることを期待している。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Boolean satisfiability is a propositional logic problem of interest in
multiple fields, e.g., physics, mathematics, and computer science. Beyond a
field of research, instances of the SAT problem, as it is known, require
efficient solution methods in a variety of applications. It is the decision
problem of determining whether a Boolean formula has a satisfying assignment,
believed to require exponentially growing time for an algorithm to solve for
the worst-case instances. Yet, the efficient solution of many classes of
Boolean formulae eludes even the most successful algorithms, not only for the
worst-case scenarios, but also for typical-case instances. Here, we introduce a
memory-assisted physical system (a digital memcomputing machine) that, when its
non-linear ordinary differential equations are integrated numerically, shows
evidence for polynomially-bounded scalability while solving "hard"
planted-solution instances of SAT, known to require exponential time to solve
in the typical case for both complete and incomplete algorithms. Furthermore,
we analytically demonstrate that the physical system can efficiently solve the
SAT problem in continuous time, without the need to introduce chaos or an
exponentially growing energy. The efficiency of the simulations is related to
the collective dynamical properties of the original physical system that
persist in the numerical integration to robustly guide the solution search even
in the presence of numerical errors. We anticipate our results to broaden
research directions in physics-inspired computing paradigms ranging from theory
to application, from simulation to hardware implementation.
- Abstract（参考訳）: ブール充足可能性(boolean satisfiability)は、物理学、数学、計算機科学など多分野に興味を持つ命題論理問題である。
研究分野の他に、SAT問題のインスタンスは、知られているように、様々なアプリケーションにおいて効率的な解法を必要とする。
ブール式が満足な代入を持つかどうかを決定する決定問題であり、最悪の場合においてアルゴリズムが解くのに指数関数的に増加する時間を必要とすると考えられている。
しかし、ブール公式の多くのクラスの効率的な解法は、最も成功したアルゴリズムでさえも、最悪のケースのシナリオだけでなく、典型的なケースのインスタンスに対しても引き出す。
本稿では,非線型常微分方程式を数値的に積分したメモリ支援物理システム(デジタルメモリ計算機)を提案する。これは,完全かつ不完全アルゴリズムの典型的な場合において,指数時間を要するSATの「ハード」植込み解のインスタンスを解きながら多項式境界拡張性を示すものである。
さらに,この物理系がカオスや指数的に増大するエネルギーを導入することなく,SAT問題を連続的に効率的に解くことを解析的に実証した。
シミュレーションの効率は、数値積分において持続する元の物理系の集合力学特性と関係し、数値誤差が存在する場合でも解探索をロバストに導く。
我々は、理論から応用まで、シミュレーションからハードウェア実装まで、物理学に触発されたコンピューティングパラダイムの研究の方向性を広げるために、結果を期待する。
関連論文リスト
- Shadow Quantum Linear Solver: A Resource Efficient Quantum Algorithm for Linear Systems of Equations [0.8437187555622164]
本稿では,デジタル量子デバイス上での量子線形システム問題(QLSP)の解法を提案する。
その結果、大きな制御されたユニタリの必要性を回避し、システムサイズで対数的な多くの量子ビットを必要とする量子アルゴリズムが実現した。
これを、線形代数の分解定理を利用して、2次元格子における離散化されたラプラス方程式を解くことで、実用的妥当性の物理問題に適用する。
論文 参考訳（メタデータ） (2024-09-13T15:46:32Z) - 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) - NeuralStagger: Accelerating Physics-constrained Neural PDE Solver with
Spatial-temporal Decomposition [67.46012350241969]
本稿では,NeuralStaggerと呼ばれる一般化手法を提案する。
元の学習タスクをいくつかの粗い解像度のサブタスクに分解する。
本稿では,2次元および3次元流体力学シミュレーションにおけるNeuralStaggerの適用例を示す。
論文 参考訳（メタデータ） (2023-02-20T19:36:52Z) - On Robust Numerical Solver for ODE via Self-Attention Mechanism [82.95493796476767]
我々は,内在性雑音障害を緩和し,AIによって強化された数値解法を,データサイズを小さくする訓練について検討する。
まず,教師付き学習における雑音を制御するための自己認識機構の能力を解析し,さらに微分方程式の数値解に付加的な自己認識機構を導入し,簡便かつ有効な数値解法であるAttrを提案する。
論文 参考訳（メタデータ） (2023-02-05T01:39:21Z) - Solving Subset Sum Problems using Quantum Inspired Optimization
Algorithms with Applications in Auditing and Financial Data Analysis [2.0981723008692392]
Hopfield Networksの勾配勾配勾配が、人工データと実データの両方の解を確実に見つける方法を示す。
本稿では,このアルゴリズムを断熱量子コンピュータに応用する方法を概説する。
論文 参考訳（メタデータ） (2022-10-28T12:22:15Z) - Message Passing Neural PDE Solvers [60.77761603258397]
我々は、バックプロップ最適化されたニューラル関数近似器で、グラフのアリーデザインのコンポーネントを置き換えるニューラルメッセージパッシング解決器を構築した。
本稿では, 有限差分, 有限体積, WENOスキームなどの古典的手法を表現的に含んでいることを示す。
本研究では, 異なる領域のトポロジ, 方程式パラメータ, 離散化などにおける高速, 安定, 高精度な性能を, 1次元, 2次元で検証する。
論文 参考訳（メタデータ） (2022-02-07T17:47:46Z) - Probabilistic ODE Solutions in Millions of Dimensions [19.09929271850469]
本稿では,確率論的数値アルゴリズムを用いて高次元ODEを解くための数学的仮定と詳細な実装手法を説明する。
これはそれまで、各解法における行列行列演算により不可能であった。
数百万次元の微分方程式の確率論的数値シミュレーションを含む,様々な問題に対する結果の効率性を評価する。
論文 参考訳（メタデータ） (2021-10-22T14:35:45Z) - Transformer-based Machine Learning for Fast SAT Solvers and Logic
Synthesis [63.53283025435107]
CNFベースのSATとMaxSATは論理合成と検証システムの中心である。
そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
論文 参考訳（メタデータ） (2021-07-15T04:47:35Z) - Directed percolation and numerical stability of simulations of digital
memcomputing machines [8.761355402590105]
DMM(Digital memcomputing Machine)は、最適化問題を解決するために設計された新しい非解決型マシンである。
これらのマシンは、メモリを持つ連続時間非量子力学系で物理的に実現することができる。
多くの困難問題の解は、DMMのODEを数値的に統合することによって報告されている。
論文 参考訳（メタデータ） (2021-02-06T09:44:28Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Stable Implementation of Probabilistic ODE Solvers [27.70274403550477]
常微分方程式(odes)の確率的解法は、数値の不確かさの効率的な定量化をもたらす。
それらは高い順序でまたは小さいステップ サイズと動くとき数値不安定に苦しみます。
本研究は,この問題に対する解決策を提案し,検討する。
正確な初期化、数値安定性をステップサイズ非依存にする座標変更事前条件、平方根実装の3つのコンポーネントを含んでいる。
論文 参考訳（メタデータ） (2020-12-18T08:35:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。