Improving known solutions is hard (Q687508)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Improving known solutions is hard |
scientific article; zbMATH DE number 431313
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Improving known solutions is hard |
scientific article; zbMATH DE number 431313 |
Statements
Improving known solutions is hard (English)
0 references
18 October 1993
0 references
The difficulty of optimization problems is studied using the ``counterexample'' model introduced by \textit{J. Krajiček}, \textit{P. Pudlák}, \textit{J. Sgall} [Interactive Computation of Optimal Solutions, Lect. Notes Comput. Sci. 452, 48-60 (1990; Zbl 0733.68041)]. Lower bounds on the number of counterexamples required to compute the optimum solutions for LEXMAXSAT and MINTSP are provided. Furthermore, sharp bounds for the computation of the optimum solution for several graph- theoretic NP-optimization problems as MAXCLIQUE are derived. The results hold even in the presence of randomness.
0 references
maximum clique
0 references
LEXMAXSAT
0 references
NP-optimization problems
0 references
0 references
