Improving known solutions is hard |
| |
Authors: | Desh Ranjan Suresh Chari Pankaj Rohatgi |
| |
Affiliation: | (1) Department of Computer Science, Cornell University, 14853 Ithaca, NY, USA |
| |
Abstract: | In this paper, we study the complexity of computing better solutions to optimization problems given other solutions. We use a model of computation suitable for this purpose, the counterexample computation model. We first prove that, if PH
P
3
, polynomial time transducers cannot compute optimal solutions for many problems, even givenn
1–
non-trivial solutions, for any >0. These results are then used to establish sharp lower bounds for several problems in the counterexample model. We extend the model by defining probabilistic counterexample computations and show that our results hold even in the presence of randomness. |
| |
Keywords: | 68Q05 68Q15 |
本文献已被 SpringerLink 等数据库收录! |
|