ON THE COMPLEXITY OF COMPUTING OPTIMAL SOLUTIONS

DOI10.1142/S0129054191000133MaRDI QIDQ4007852zbMATH OpenOpenAlexFDO

Authors Zhi-Zhong Chen, Seinosuke Toda

Publication date 27 September 1992

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054191000133

zbMATH Keywords

computational complexity theorynon-deterministic polynomial timepolynomial paddabilityrandomized algorithmtruth-table reducibility

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The complexity of optimization problems
• scientific article; zbMATH DE number 809154
• Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems
• Functions computable with nonadaptive queries to NP
• Complexity of Counting the Optimal Solutions

Cited in

(19)

• The computational complexity of maximization and integration
• Area-time complexity of the unconstrained minimization problem
• The complexity of optimization problems
• Improving the complexities of approximation algorithms for optimization problems
• A computing experiment in the problem of optimization of computations. I
• The complexity of comparing optimal solutions
• Preimage problems for reaction systems
• Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
• scientific article; zbMATH DE number 5799870 (Why is no real title available?)
• scientific article; zbMATH DE number 4213452 (Why is no real title available?)
• scientific article; zbMATH DE number 1822170 (Why is no real title available?)
• scientific article; zbMATH DE number 809154 (Why is no real title available?)
• scientific article; zbMATH DE number 5204606 (Why is no real title available?)
• Improving known solutions is hard
• Structure of polynomial-time approximation
• Ancestors, descendants, and gardens of Eden in reaction systems
• Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems
• On complexity of a global optimization problem
• On the complexity of optimization over the standard simplex

This page was built for publication: ON THE COMPLEXITY OF COMPUTING OPTIMAL SOLUTIONS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4007852)