Improving known solutions is hard (Q687508)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Improving known solutions is hard |
scientific article |
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
