Preprocessing of intractable problems

Technical Report, Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza"

Some computationally hard problems -e.g., deduction in logical knowledge bases- are such that part of an instance is known well before the rest of it, and remains the same for several subsequent instances of the problem. In these cases, it is meaningful to preprocess off-line this known part so as to simplify the remaining on-line problem. In this paper we investigate such a technique in the context of intractable, i.e., NP-hard, problems. Recent results in the literature show that not all NP-hard problems behave in the same way: for some of them preprocessing yields polynomial-time on-line simplified problems (we call them compilable), while for other ones there is strong evidence that this should not happen. Our primary goal is to provide a sound methodology that can be used either to prove or disprove that a problem is compilable. To this end, we define new models of computation, complexity classes, and reductions. We find complete problems for such classes, completeness meaning they are "the less likely to be compilable". We also investigate preprocessing that does not yield polynomial-time on-line algorithms, but generically "decreases" complexity. This leads us to define "hierarchies of compilability", that are the analog of the polynomial hierarchy. A detailed comparison of our framework to the related idea of "parameterized tractability" shows the differences between the two approaches.

 @techreport{cado-etal-97-d,
 title = {Preprocessing of intractable problems},
 year = {1997},
 author = {Cadoli, Marco and Donini, Francesco M. and Liberatore, Paolo and
 Schaerf, Marco},
 institution = {Dipartimento di Informatica e Sistemistica, Universit\`a di Roma "La
 Sapienza"},
 number = {DIS 24-97},
 }