Monotonic Reductions, Representative Equivalence, and Compilation of Intractable Problems

Paolo Liberatore

Journal of the ACM

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 paper we show sufficient conditions to prove that an intractable problem cannot be efficiently solved even allowing an exponentially long preprocessing phase. The generality of such conditions is shown by applying them to various problems coming from different fields. While the results may seem to discourage the use of compilation, we present some evidence that such negative results are useful in practice.


 @article{libe-01,
 title = {Monotonic Reductions, Representative Equivalence, and Compilation of
 Intractable Problems},
 year = {2001},
 author = {Liberatore, Paolo},
 journal = {Journal of the ACM},
 pages = {1091-1125},
 number = {6},
 volume = {48},
 }
 
HTTP download.
doi: 10.1145/504794.504795