The complexity of optimization problems
From MaRDI portal
Recommendations
- ON THE COMPLEXITY OF COMPUTING OPTIMAL SOLUTIONS
- scientific article; zbMATH DE number 846225
- On complexity of a global optimization problem
- Complexity analysis for optimization methods
- scientific article; zbMATH DE number 501506
- Complexity and algorithms for nonlinear optimization problems
- scientific article; zbMATH DE number 6832021
- Complexity results for some global optimization problems
- The complexity of comparing optimal solutions
- scientific article; zbMATH DE number 429516
Cites work
- Alternation
- Generalizations of Opt P to the polynomial hierarchy
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1303203 (Why is no real title available?)
- NP is as easy as detecting unique solutions
- On Isomorphisms and Density of NP and Other Complete Sets
- On the complexity of unique solutions
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Some simplified NP-complete graph problems
- The complexity of computing the permanent
- The complexity of facets (and some facets of complexity)
- The complexity of optimization problems
- The complexity of theorem-proving procedures
- The NP-completeness column: an ongoing guide
- The polynomial-time hierarchy
Cited in
(only showing first 100 items - show all)- The complexity of power-index comparison
- Before and after vacuity
- Theory of one-tape linear-time Turing machines
- The computational complexity of maximization and integration
- Polynomial terse sets
- Geometric optimization and \(D^ P\)-completeness
- The complexity of optimization problems
- Nondeterministic bounded query reducibilities
- \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems
- Bounded queries to SAT and the Boolean hierarchy
- Constructive complexity
- Optimization, approximation, and complexity classes
- Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
- Generalizations of Opt P to the polynomial hierarchy
- Traveling salesman problem and local search
- On the complexity of propositional knowledge base revision, updates, and counterfactuals
- A very hard log-space counting class
- Quantifiers and approximation
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- The complexity of computing maximal word functions
- A taxonomy of complexity classes of functions
- The complexity of optimizing finite-state transducers
- Simple characterizations of \(P(\# P)\) and complete problems
- Universally serializable computation
- Studying the complexity of global verification for NP-hard discrete optimization problems
- Optimal satisfiability for propositional calculi and constraint satisfaction problems.
- Some connections between bounded query classes and non-uniform complexity.
- The complexity of belief update
- Some structural properties of SAT
- Default reasoning from conditional knowledge bases: Complexity and tractable cases
- Extending and implementing the stable model semantics
- Some new results in the complexity of allocation and binding in data path synthesis
- Minimal sets on propositional formulae. Problems and reductions
- Probabilistic spatio-temporal knowledge bases: capacity constraints, count queries, and consistency checking
- The complexity of error metrics
- On the complexity of finding the chromatic number of a recursive graph. I: The bounded case
- On the complexity of data disjunctions.
- Bounded queries, approximations, and the Boolean hierarchy
- Optimal series-parallel trade-offs for reducing a function to its own graph
- On the power of unambiguity in log-space
- Non-uniform reductions
- Two queries
- Fortran subroutines for computing approximate solutions of weighted MAX-SAT problems using GRASP
- The value of help bits in randomized and average-case complexity
- A nondeterministic Turing machine variant to compute functions
- Choice logics and their computational properties
- The variational quantum eigensolver: a review of methods and best practices
- On the complexity of validity degrees in Łukasiewicz logic
- Timed negotiations
- Computing homotopic line simplification
- Monodirectional P systems
- A complexity theory for feasible closure properties
- Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
- Efficient timed model checking for discrete-time systems
- Reductions between disjoint NP-pairs
- From causes for database queries to repairs and model-based diagnosis and back
- A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison
- Consistency checking and querying in probabilistic databases under integrity constraints
- Proving SAT does not have small circuits with an application to the two queries problem
- On the query complexity of selecting minimal sets for monotone predicates
- Pure Nash equilibria in a generalization of congestion games allowing resource failures
- The complexity of comparing optimal solutions
- Complexity of manipulative interference in participatory budgeting
- Complexity and approximability of quantified and stochastic constraint satisfaction problems
- Preimage problems for reaction systems
- Heuristic NPN classification for large functions using AIGs and LEXSAT
- On the complexity of master problems
- Function operators spanning the arithmetical and the polynomial hierarchy
- The complexity of finding \(k\)th most probable explanations in probabilistic networks
- scientific article; zbMATH DE number 6832021 (Why is no real title available?)
- The Power of Self-Reducibility: Selectivity, Information, and Approximation
- Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
- Computing maximal autarkies with few and simple oracle queries
- Weighted Boolean formula games
- Complexity of Counting the Optimal Solutions
- Counting Complexity of Minimal Cardinality and Minimal Weight Abduction
- Model Checking FO(R) over One-Counter Processes and beyond
- scientific article; zbMATH DE number 3965441 (Why is no real title available?)
- ON THE COMPLEXITY OF COMPUTING OPTIMAL SOLUTIONS
- A survey of one-way functions in complexity theory
- Structural analysis of the complexity inverse functions
- scientific article; zbMATH DE number 501506 (Why is no real title available?)
- Generalized theorems on relationships among reducibility notions to certain complexity classes
- Most probable explanations in Bayesian networks: complexity and tractability
- Quantum optimization problems
- Complexity results for some eigenvector problems
- UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS
- scientific article; zbMATH DE number 6970794 (Why is no real title available?)
- The consequences of eliminating NP solutions
- A survey on the structure of approximation classes
- Polynomially bounded minimization problems which are hard to approximate
- Reasoning with uncertain and inconsistent OWL ontologies
- On computing Boolean connectives of characteristic functions
- scientific article; zbMATH DE number 809154 (Why is no real title available?)
- Two hardness results for Gamson's game
- Tailoring recursion for complexity
- On the complexity of inverse mixed integer linear optimization
- The operators min and max on the polynomial hierarchy
- Resource-bounded Kolmogorov complexity revisited
- The complexity class θp2: Recent results and applications in AI and modal logic
This page was built for publication: The complexity of optimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1107309)