The complexity of optimization problems
type: Item
instance of: scholarly article
title: The complexity of optimization problems
zbMATH Open document ID: 0652.68040
DOI: 10.1016/0022-0000(88)90039-6
author: Mark W. Krentel
published in: Journal of Computer and System Sciences
publication date: 1988-01-01T00:00:00Z
full work available at URL: https://hdl.handle.net/1813/6559
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 4064471
zbMATH Keywords: NP-complete optimization problems
zbMATH Keywords: Traveling salesperson
zbMATH Keywords: Knapsack
zbMATH Keywords: Clique
zbMATH Keywords: Coloring
zbMATH Keywords: Bin packing
MaRDI profile type: Publication
OpenAlex ID: W2072181151
cites work: Q4091421
cites work: Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: Alternation
cites work: The complexity of theorem-proving procedures
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: Q4249726
cites work: The NP-completeness column: an ongoing guide
cites work: Q4142699
cites work: Generalizations of Opt P to the polynomial hierarchy
cites work: On the complexity of unique solutions
cites work: The complexity of facets (and some facets of complexity)
cites work: The polynomial-time hierarchy
cites work: The complexity of computing the permanent
cites work: NP is as easy as detecting unique solutions
Recommended article: ON THE COMPLEXITY OF COMPUTING OPTIMAL SOLUTIONS
Recommended article: Q4864690
Recommended article: On complexity of a global optimization problem
Recommended article: Complexity analysis for optimization methods
Recommended article: Q4279211
Recommended article: Complexity and algorithms for nonlinear optimization problems
Recommended article: Q3132650
Recommended article: Complexity results for some global optimization problems
Recommended article: The complexity of comparing optimal solutions
Recommended article: Q3137900
description: scientific article; zbMATH DE number 4064471