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...

Full description

Bibliographic Details

Published in:	Journal of the ACM 48, 6 (2001).
Main Author:	Liberatore, P.
Format:	Article
Language:	English
Subjects:	Theory of computation. Analysis of algorithms and problem complexity. Nonnumerical algorithms and problems. Computing methodologies. Artificial intelligence. Problem solving, control methods and search. Algorithms. Theory.