Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems

DOI10.1016/0020-0190(90)90188-4MaRDI QIDQ915446zbMATH OpenOpenAlexFDO

Authors Pilu Crescenzi, Riccardo Silvestri

Publication date 1990

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(90)90188-4

zbMATH Keywords

many-one reducibilityNP-complete problemoptimization problemTuring reducibility

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• ON THE COMPLEXITY OF COMPUTING OPTIMAL SOLUTIONS
• The complexity of optimization problems
• scientific article; zbMATH DE number 515727
• scientific article; zbMATH DE number 809154
• The computational complexity of maximization and integration

Cites work

• Combinatorial problems over power sets
• Complexity of Presburger arithmetic with fixed quantifier dimension
• scientific article; zbMATH DE number 3984573 (Why is no real title available?)
• scientific article; zbMATH DE number 1303203 (Why is no real title available?)
• On gamma-reducibility versus polynomial time many-one reducibility
• Relative complexity of checking and evaluating
• Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems

Cited in

(8)

• On the computational complexity of cost efficiency analysis models
• The complexity of comparing optimal solutions
• On the relative complexity of 15 problems related to~0/1-integer programming
• Integer Programming: Optimization and Evaluation Are Equivalent
• ON THE COMPLEXITY OF COMPUTING OPTIMAL SOLUTIONS
• A note on the depth function of combinatorial optimization problems
• Approximate solution of NP optimization problems
• Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems

This page was built for publication: Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems

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