Monotonic reductions, representative equivalence and compilation of intractable problems.
The idea of preprocessing part of the input of a problem in order to improve efficiency has been employed by several researchers in several areas of computer science. In this article, we show sufficient conditions to prove that an intractable problem cannot be efficiently solved even allowing an exp...
| Publicado no: | Journal of the ACM 48, 6 (2001). |
|---|---|
| Autor principal: | |
| Formato: | Artigo |
| Idioma: | English |
| Assuntos: |