論文の概要: Linear Equations with Min and Max Operators: Computational Complexity

• arxiv url: http://arxiv.org/abs/2412.12228v1
• Date: Mon, 16 Dec 2024 12:18:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-18 13:57:16.087575
• Title: Linear Equations with Min and Max Operators: Computational Complexity
• Title（参考訳）: Min および Max 演算子を用いた線形方程式:計算複雑性
• Authors: Krishnendu Chatterjee, Ruichen Luo, Raimundo Saona, Jakub Svoboda,
• Abstract要約: min および max 演算子を持つ線形方程式系によって定義される最適化問題のクラスを考える。 条件 C2 と C4 ではNP完全であるのに対し、条件 C1 では UP は coUP と交差する。
• 参考スコア（独自算出の注目度）: 5.0710622093569055
• License:
• Abstract: We consider a class of optimization problems defined by a system of linear equations with min and max operators. This class of optimization problems has been studied under restrictive conditions, such as, (C1) the halting or stability condition; (C2) the non-negative coefficients condition; (C3) the sum up to 1 condition; and (C4) the only min or only max oerator condition. Several seminal results in the literature focus on special cases. For example, turn-based stochastic games correspond to conditions C2 and C3; and Markov decision process to conditions C2, C3, and C4. However, the systematic computational complexity study of all the cases has not been explored, which we address in this work. Some highlights of our results are: with conditions C2 and C4, and with conditions C3 and C4, the problem is NP-complete, whereas with condition C1 only, the problem is in UP intersects coUP. Finally, we establish the computational complexity of the decision problem of checking the respective conditions.
• Abstract（参考訳）: min および max 演算子を持つ線形方程式系によって定義される最適化問題のクラスを考える。 このタイプの最適化問題は、(C1)停止状態または安定性条件、(C2)非負係数条件、(C3)和を1条件まで、(C4)唯一の最小または極大エウレータ条件などの制限条件下で研究されている。 文学におけるいくつかの初歩的な成果は、特別な事例に焦点を当てている。 例えば、ターンベースの確率ゲームは条件 C2 と C3 に対応し、マルコフ決定プロセスは条件 C2, C3, C4 に対応する。 しかし、全てのケースの体系的な計算複雑性の研究は行われておらず、本研究で論じる。 条件 C2 と C4 と条件 C3 と C4 ではNP完全であるのに対し、条件 C1 では UP は coUP と交差する。 最後に,各条件を判定する決定問題の計算複雑性を確立する。

関連論文リスト

• Applying the quantum approximate optimization algorithm to general constraint satisfaction problems [0.0]
  ランダム制約満足度問題(CSP)に適用した場合に量子近似最適化(QAOA)の性能を解析するための理論的手法を開発する。 提案手法により,ランダムに生成されたCSPのインスタンスに適用した場合に,各レイヤとパラメータを用いてQAOAの成功確率を計算することができる。 ランダムな$k$-SATは、QAOAを用いた量子古典的分離を示す上で、これらのCSPの中で最も有望であると考えられる。
  論文  参考訳（メタデータ） (2024-11-26T14:00:34Z)
• Chain of Condition: Construct, Verify and Solve Conditions for Conditional Question Answering [34.599299893060895]
  条件付き質問応答(CQA)は、可能な回答を見つけ、不足した条件を特定することを目的とした重要なタスクである。 既存のアプローチは,(1)必要な条件と論理的関係を正確に同定し,(2)不足しているものを検出するための条件を検証するという2つの課題により,CQAと競合する。 本論文では,まずすべての条件を同定し,それらの論理的関係を文書に従って明示的に構築することで,新しい条件の連鎖を創出する手法を提案する。
  論文  参考訳（メタデータ） (2024-08-10T05:09:11Z)
• First-order optimality conditions for non-commutative optimization problems [0.0]
  非可換変数の導出状態平均を最適化する問題を考察する。 状態最適条件はすべてのNPO問題によって満たされる。 作用素最適条件はカルーシュ=クーン=タッカー条件の非可換類似である。
  論文  参考訳（メタデータ） (2023-11-30T17:00:06Z)
• Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints [16.96067869451225]
  単ループ2次ペナルティと拡張ヴァリガングアルゴリズムの複雑さを解析する。 目的が関数的かつ滑らかな3つの場合を考える。
  論文  参考訳（メタデータ） (2023-11-01T17:37:41Z)
• Minimax Instrumental Variable Regression and $L_2$ Convergence Guarantees without Identification or Closedness [71.42652863687117]
  インストゥルメンタル変数(IV)回帰の非パラメトリック推定について検討した。 固定IV解に収束できる新しいペナル化ミニマックス推定器を提案する。 ラックス条件下での推定値に対して強い$L$誤差率を導出する。
  論文  参考訳（メタデータ） (2023-02-10T18:08:49Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)
• On the Complexity of a Practical Primal-Dual Coordinate Method [63.899427212054995]
  ランダム・座標降下法(PURE-CD)を用いた原始双対アルゴリズムの複雑性境界を証明した。 バイマックス性能問題を解くための優れた外挿が得られることが示されている。
  論文  参考訳（メタデータ） (2022-01-19T16:14:27Z)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  機械学習に多くの応用がある非SBO問題を考察する。 本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-05T18:28:42Z)
• Quantum Constraint Problems can be complete for $\mathsf{BQP}$, $\mathsf{QCMA}$, and more [0.0]
  量子制約問題はすべて、古典的制約問題と共有されない性質である量子ビット上で実現可能であることを示す。 結果は、量子制約問題に存在するクラスの顕著な多様性を示唆している。
  論文  参考訳（メタデータ） (2021-01-21T01:08:04Z)
• Gradient-Free Methods for Saddle-Point Problem [125.99533416395765]
  我々はGasnikov et al., 2017のアプローチを一般化し、不正確な勾配のないオラクルで(確率的な)凸最適化問題を解けるようにした。 我々のアプローチは、$fracnlog n$ の要求するオラクル呼び出しの回数を削減します。 論文の後半では、そのような仮定ができない場合を分析し、この問題を解決する方法の近代化方法に関する一般的なアプローチを提案する。
  論文  参考訳（メタデータ） (2020-05-12T16:44:27Z)

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

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