論文の概要: Translationally Invariant Constraint Optimization Problems
- arxiv url: http://arxiv.org/abs/2209.08731v1
- Date: Mon, 19 Sep 2022 03:03:05 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-26 02:29:15.050618
- Title: Translationally Invariant Constraint Optimization Problems
- Title（参考訳）: 翻訳不変制約最適化問題
- Authors: Dorit Aharonov and Sandy Irani
- Abstract要約: 2次元格子上の古典的制約満足度問題の複雑性について検討する。
この問題は、古典物理学における最も興味深い問題の1つ、すなわち格子上の古典的な粒子系の最低エネルギーの計算と等価である。
我々は、$N倍のN$グリッドに対して、$Omega(N1/4)$という加算誤差の範囲内で最適な割り当てのコストを近似するのはNEXPハードであることを示す。
- 参考スコア（独自算出の注目度）: 0.7863638253070437
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the complexity of classical constraint satisfaction problems on a 2D
grid. Specifically, we consider the complexity of function versions of such
problems, with the additional restriction that the constraints are
translationally invariant, namely, the variables are located at the vertices of
a 2D grid and the constraint between every pair of adjacent variables is the
same in each dimension. The only input to the problem is thus the size of the
grid. This problem is equivalent to one of the most interesting problems in
classical physics, namely, computing the lowest energy of a classical system of
particles on the grid. We provide a tight characterization of the complexity of
this problem, and show that it is complete for the class $FP^{NEXP}$. Gottesman
and Irani (FOCS 2009) also studied classical translationally-invariant
constraint satisfaction problems; they show that the problem of deciding
whether the cost of the optimal solution is below a given threshold is
NEXP-complete. Our result is thus a strengthening of their result from the
decision version to the function version of the problem. Our result can also be
viewed as a generalization to the translationally invariant setting, of
Krentel's famous result from 1988, showing that the function version of SAT is
complete for the class $FP^{NP}$. An essential ingredient in the proof is a
study of the complexity of a gapped variant of the problem. We show that it is
NEXP-hard to approximate the cost of the optimal assignment to within an
additive error of $\Omega(N^{1/4})$, for an $N \times N$ grid. To the best of
our knowledge, no gapped result is known for CSPs on the grid, even in the
non-translationally invariant case. As a byproduct of our results, we also show
that a decision version of the optimization problem which asks whether the cost
of the optimal assignment is odd or even is also complete for $P^{NEXP}$.
- Abstract（参考訳）: 2次元格子上の古典的制約満足度問題の複雑性について検討する。
具体的には、これらの問題の関数のバージョンの複雑さを考慮し、制約が翻訳的に不変であるという追加の制約、すなわち変数は2次元グリッドの頂点に位置し、隣接する変数のペア間の制約は各次元において同じである。
問題への唯一の入力はグリッドのサイズである。
この問題は、古典物理学における最も興味深い問題の1つ、すなわち格子上の古典的な粒子系の最低エネルギーの計算と等価である。
この問題の複雑さの厳密な特徴づけを提供し、クラス$FP^{NEXP}$に対して完備であることを示す。
ゴッテマンとイラン人(focs 2009)も古典的翻訳不変制約満足問題を研究し、最適解のコストが与えられたしきい値以下かどうかを決定する問題はnexp完全であることを示した。
その結果、決定版から問題の関数版への結果の強化が図られた。
我々の結果は、1988年のクレンテルの有名な結果の翻訳不変集合への一般化と見なすことができ、SAT の函数バージョンがクラス $FP^{NP}$ に対して完備であることを示す。
この証明の必須成分は、問題のガッピング変種(gapped variant)の複雑さの研究である。
我々は、$N \times N$ gridに対して、$\Omega(N^{1/4})$の加算誤差の範囲内で最適な割り当てのコストを近似することはNEXPハードであることが示される。
我々の知る限りでは、非翻訳不変の場合においても、グリッド上のCSPに対してギャップのある結果は知られていない。
結果の副産物として、最適割り当てのコストが奇数かどうかを問う最適化問題の決定版が$P^{NEXP}$でも完備であることを示す。
関連論文リスト
- One for All: Universal Quantum Conic Programming Framework for Hard-Constrained Combinatorial Optimization Problems [0.0]
NP完全制約最適化問題を解くための統一量子古典的枠組みを提案する。
QCPのパラメータ化アンサッツクラスは、生成したサブコーン内の最適値を常にキャプチャすることを示す。
論文 参考訳（メタデータ） (2024-11-01T08:00:30Z) - 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) - Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions [18.086061048484616]
平衡問題の幅広いクラスをモデル化した有限サム単調包含問題について検討する。
我々の主な貢献は、複雑性の保証を改善するために分散還元を利用する古典的ハルパーン反復の変種である。
我々は、この複雑さが単調なリプシッツ設定では改善できないと論じる。
論文 参考訳（メタデータ） (2023-10-04T17:24:45Z) - Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳（メタデータ） (2023-07-17T09:55:35Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - Minimizing low-rank models of high-order tensors: Hardness, span, tight
relaxation, and applications [26.602371644194143]
この基本テンソル問題は 1 以上のテンソル階数に対して NP-hard であることを示す。
低次ランクの場合、提案された連続的な再構成は低複素度勾配に基づく最適化に有効である。
低密度パリティチェックコードや一般復号パリティチェックコードなど,多くの難題に対する有望な結果を示す。
論文 参考訳（メタデータ） (2022-10-16T11:53:42Z) - Gradient-Free Methods for Deterministic and Stochastic Nonsmooth
Nonconvex Optimization [94.19177623349947]
非滑らかな非最適化問題は、機械学習とビジネス製造に現れる。
2つのコア課題は、有限収束を保証する効率的な方法の開発を妨げる。
GFMとSGFMの2相版も提案され, 改良された大規模評価結果が得られた。
論文 参考訳（メタデータ） (2022-09-12T06:53:24Z) - Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results
and Construction [18.65143269806133]
我々は、個々のコンポーネントごとに勾配および近位オラクルにアクセスできる近位インクリメンタルファーストオーダー(PIFO)アルゴリズムを検討する。
古典的な例の三対角行列を$n$群に分割する逆問題を構築するための新しいアプローチを開発する。
論文 参考訳（メタデータ） (2021-03-15T11:20:31Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳（メタデータ） (2020-04-25T05:45:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。