Linear Equations with Min and Max Operators: Computational Complexity

• URL: http://arxiv.org/abs/2412.12228v1
• Date: Mon, 16 Dec 2024 12:18:36 GMT
• Title: Linear Equations with Min and Max Operators: Computational Complexity
• Authors: Krishnendu Chatterjee, Ruichen Luo, Raimundo Saona, Jakub Svoboda,
• Abstract summary: We consider a class of optimization problems defined by a system of linear equations with min and max operators. Some highlights of our results are: with conditions C2 and C4, the problem is NP-complete, whereas with condition C1 only, the problem is in UP intersects coUP.
• Score: 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.

Related papers

• Applying the quantum approximate optimization algorithm to general constraint satisfaction problems [0.0]
  We develop theoretical techniques for analysing the performance of the quantum approximate optimization (QAOA) when applied to random constraint satisfaction problems (CSPs) Our techniques allow us to compute the success probability of QAOA with one layer and given parameters, when applied to randomly generated instances of CSPs. We find that random $k$-SAT seems to be the most promising of these CSPs for demonstrating a quantum-classical separation using QAOA.
  arXiv  Detail & Related papers  (2024-11-26T14:00:34Z)
• Chain of Condition: Construct, Verify and Solve Conditions for Conditional Question Answering [34.599299893060895]
  Conditional question answering (CQA) is an important task that aims to find probable answers and identify missing conditions. Existing approaches struggle with CQA due to two challenges: (1) precisely identifying necessary conditions and the logical relationship, and (2) verifying conditions to detect any that are missing. We propose a novel prompting approach, Chain of condition, by first identifying all conditions and constructing their logical relationships explicitly according to the document.
  arXiv  Detail & Related papers  (2024-08-10T05:09:11Z)
• First-order optimality conditions for non-commutative optimization problems [0.0]
  We consider the problem of optimizing the state average of a derivation of non-commuting variables. State optimality conditions are shown to be satisfied by all NPO problems. Operator optimality conditions are the non-commutative analogs of the Karush-Kuhn-Tucker conditions.
  arXiv  Detail & Related papers  (2023-11-30T17:00:06Z)
• Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints [16.96067869451225]
  We analyze the complexity of single-loop quadratic penalty and augmented Varigrangian algorithms. We consider three cases, in which the objective is functional and smooth that is an expectation over an unknown distribution.
  arXiv  Detail & Related papers  (2023-11-01T17:37:41Z)
• Minimax Instrumental Variable Regression and $L_2$ Convergence Guarantees without Identification or Closedness [71.42652863687117]
  We study nonparametric estimation of instrumental variable (IV) regressions. We propose a new penalized minimax estimator that can converge to a fixed IV solution. We derive a strong $L$ error rate for our estimator under lax conditions.
  arXiv  Detail & Related papers  (2023-02-10T18:08:49Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  In this paper we consider finding an approximate second-order stationary point (SOSP) that minimizes a twice different subject general non conic optimization. In particular, we propose a Newton-CG based-augmentedconjugate method for finding an approximate SOSP.
  arXiv  Detail & Related papers  (2023-01-10T20:43:29Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• On the Complexity of a Practical Primal-Dual Coordinate Method [63.899427212054995]
  We prove complexity bounds for primal-dual algorithm with random and coordinate descent (PURE-CD) It has been shown to obtain good extrapolation for solving bi-max performance problems.
  arXiv  Detail & Related papers  (2022-01-19T16:14:27Z)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  We consider non-SBO problems that have many applications in machine learning. This paper proposes fast randomized algorithms for non-SBO problems.
  arXiv  Detail & Related papers  (2021-05-05T18:28:42Z)
• Quantum Constraint Problems can be complete for $\mathsf{BQP}$, $\mathsf{QCMA}$, and more [0.0]
  We show that all quantum constraint problems can be realized on qubits, a trait not shared with classical constraint problems. Results suggest a significant diversity of classes present in quantum constraint problems.
  arXiv  Detail & Related papers  (2021-01-21T01:08:04Z)
• Gradient-Free Methods for Saddle-Point Problem [125.99533416395765]
  We generalize the approach Gasnikov et. al., 2017, which allows to solve (stochastic) convex optimization problems with an inexact gradient-free oracle. Our approach reduces $fracnlog n$ times the required number of oracle calls. In the second part of the paper, we analyze the case when such an assumption cannot be made, we propose a general approach on how to modernize the method to solve this problem.
  arXiv  Detail & Related papers  (2020-05-12T16:44:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.