Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems
From MaRDI portal
Publication:915446
DOI10.1016/0020-0190(90)90188-4zbMath0702.68052OpenAlexW2060079637MaRDI QIDQ915446
Riccardo Silvestri, Pierluigi Crescenzi
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
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)
Related Items
Integer Programming: Optimization and Evaluation Are Equivalent, On the Relative Complexity of 15 Problems Related to 0/1-Integer Programming, Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems, Approximate solution of NP optimization problems
Cites Work
- Unnamed Item
- Unnamed Item
- Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems
- Combinatorial problems over power sets
- On gamma-reducibility versus polynomial time many-one reducibility
- Relative complexity of checking and evaluating
- Complexity of Presburger arithmetic with fixed quantifier dimension
