Monotonic reductions, representative equivalence, and compilation of intractable problems

ABSTRACT

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

REFERENCES

• 1: Pankaj K. Agarwal , Lars Arge , Jeff Erickson , Paulo G. Franciosa , Jeffrey Scott Vitter, Efficient searching with linear constraints, Journal of Computer and System Sciences, v.61 n.2, p.194-216, Oct. 2000 [doi>10.1006/jcss.2000.1709]
• 2: ALLEMANG, D., TANNER, M. C., BYLANDER,T.,AND JOSEPHSON, J. R. 1987. Computational complexity of hypothesis assembly. In Proceedings of the 10th International Joint Conference on Artificial Intelligence. Morgan-Kaufmann, San Mateo, Calif., pp. 1112-1117.
• 3: Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM (JACM), v.45 n.6, p.891-923, Nov. 1998 [doi>10.1145/293347.293348]
• 4: Amos Beimel , Yuval Ishai , Tal Malkin, Reducing the Servers Computation in Private Information Retrieval: PIR with Preprocessing, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.55-73, August 20-24, 2000
• 5: BOUTILIER, C. 1993. Revision sequences and nested conditionals. In Proceedings of the 13th International Joint Conference on Artificial Intelligence. Morgan-Kaufmann, San Mateo, Calif., pp. 519-525.
• 6: BYLANDER, T. 1991. Complexity results for planning. In Proceedings of the 12th International Joint Conference on Artificial Intelligence. Morgan-Kaufmann, San Mateo, Calif., pp. 274-279.
• 7: Tom Bylander , Dean Allemang , Michael C. Tanner , John R. Josephson, The computational complexity of abduction, Artificial Intelligence, v.49 n.1-3, p.25-60, May 1991 [doi>10.1016/0004-3702(91)90005-5]
• 8: Marco Cadoli , Francesco M. Donini, A survey on knowledge compilation, AI Communications, v.10 n.3-4, p.137-150, Dec. 1997
• 9: Marco Cadoli , Francesco M. Donini , Paolo Liberatore , Marco Schaerf, The size of a revised knowledge base, Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.151-162, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220205]
• 10: CADOLI, M., DONINI, F., LIBERATORE,P.,AND SCHAERF, M. 1996. Comparing space efficiency of propositional knowledge representation formalisms. In Proceedings of the 5th International Conference on the Principles of Knowledge Representation and Reasoning. Morgan-Kaufmann, San Mateo, Calif., pp. 364-373.
• 11: Marco Cadoli , Francesco M. Donini , Paolo Liberatore , Marco Schaerf, Preprocessing of intractable problems, Information and Computation, v.176 n.2, p.89-120, 01 August 2002 [doi>10.1006/inco.2001.3043]
• 12: Marco Cadoli , Francesco M. Donini , Marco Schaerf , Riccardo Silvestri, On compact representations of propositional circumscription, Theoretical Computer Science, v.182 n.1-2, p.183-202, Aug. 1997 [doi>10.1016/S0304-3975(96)00182-X]
• 13: Liming Cai , Jianer Chen , Rodney Downey , Michael Fellows, On the structure of parameterized problems in NP, Information and Computation, v.123 n.1, p.38-49, Nov. 15, 1995 [doi>10.1006/inco.1995.1156]
• 14: CAI, L., CHEN, J., DOWNEY, R., AND FELLOWS, M. 1997. Advice classes of parameterized tractability. Ann. Pure Appl. Logic 84, 119-138.
• 15: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 16: Luca Console , Luigi Portinale , Daniele Theseider Dupré, Using Compiled Knowledge to Guide and Focus Abductive Diagnosis, IEEE Transactions on Knowledge and Data Engineering, v.8 n.5, p.690-706, October 1996 [doi>10.1109/69.542024]
• 17: DECHTER, R. 1998. Constraint satisfaction. In MIT Encyclopedia of the Cognitive Sciences. Vol. Computational Intelligence. The MIT Press, Cambridge, Chap. 16, Mass. pp. 195-197.
• 18: DOWNEY,R.G.,AND FELLOWS, M. F. 1999. Parameterized Complexity. Springer-Verlag, Berlin, Germany
• 19: Thomas Eiter , Georg Gottlob, The complexity of logic-based abduction, Journal of the ACM (JACM), v.42 n.1, p.3-42, Jan. 1995 [doi>10.1145/200836.200838]
• 20: FIKES, R., AND NILSSON, N. 1971. STRIPS: A new approach to the application of theorem proving to problem solving. Artif. Int. 2, 189-208.
• 21: Zvi Galil, A constant-time optimal parallel string-matching algorithm, Journal of the ACM (JACM), v.42 n.4, p.908-918, July 1995 [doi>10.1145/210332.210341]
• 22: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 23: GELFOND, M., AND LIFSCHITZ, V. 1993. Representing action and change by logic programs. J. Logic Prog. 17, 301-322.
• 24: GOGIC, G., KAUTZ, H. A., PAPADIMITRIOU, C., AND SELMAN, B. 1995. The comparative linguistics of knowledge representation. In Proceedings of the 14th International Joint Conference on Artificial Intelligence. Morgan-Kaufmann, San Mateo, Calif., pp. 862-869.
• 25: I. Gohberg , V. Olshevsky, Fast algorithms with preprocessing for matrix-vector multiplication problems, Journal of Complexity, v.10 n.4, p.411-427, Dec. 1994 [doi>10.1006/jcom.1994.1021]
• 26: Georg Gottlob , Nicola Leone , Francesco Scarcello, The Complexity of Acyclic Conjunctive Queries, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.706, November 08-11, 1998
• 27: Klaus Jansen , Haiko Müller, The minimum broadcast time problem for several processor networks, Theoretical Computer Science, v.147 n.1-2, p.69-85, Aug. 7, 1995 [doi>10.1016/0304-3975(94)00230-G]
• 28: David S. Johnson, A catalog of complexity classes, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 29: KARP, R. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations. R. Miller and J. Thatcher, Eds. Plenum Press, New York, pp. 85-103.
• 30: KARP, R. 1975. On the computational complexity of combinatorial problems. Network 5, 45-70.
• 31: Richard M. Karp , Richard J. Lipton, Some connections between nonuniform and uniform complexity classes, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.302-309, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804678]
• 32: KAUTZ,H.A.,AND SELMAN, B. 1992. Forming concepts for fast inference. In Proceedings of the 10th National Conference on Artificial Intelligence. AAAI/MIT Press, Menlo Park, Calif., pp. 786-793.
• 33: Lydia E. Kavraki , Jean-Claude Latombe , Rajeev Motwani , Prabhakar Raghavan, Randomized query processing in robot path planning, Journal of Computer and System Sciences, v.57 n.1, p.50-60, Aug. 1998 [doi>10.1006/jcss.1998.1578]
• 34: Paolo Liberatore, The Complexity of Iterated Belief Revision, Proceedings of the 6th International Conference on Database Theory, p.276-290, January 08-10, 1997
• 35: LIBERATORE, P. 1997b. The complexity of the language A . Electron. Trans. Artif. Int. 1, 1-3, 13-37.
• 36: LIBERATORE, P. 1998a. Compilation of intractable problems and its application to Artificial Intelligence. Ph.D. dissertation, Dipartimento di Informatica e Sistemistica, Universita di Roma "La Sapienza,"Rome, Italy.
• 37: LIBERATORE, P. 1998b. On the compilability of diagnosis, planning, reasoning about actions, belief revision, etc. In Proceedings of the 6th International Conference on Principles of Knowledge Representation and Reasoning. Morgan-Kaufmann, San Mateo, Calif., pp. 144-155.
• 38: LIBERATORE, P. 1999. Monotonic reductions, representative equivalence, and compilation of intractable problems. Tech. Rep. 30-99, Dipartimento di Informatica e Sistemistica, Universita di Roma "La Sapienza," Rome, Italy.
• 39: Paolo Liberatore , Marco Schaerf, Compilability of Abduction, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.349-354, July 30-August 03, 2000
• 40: MCILRAITH, S. 1998. Logic-based abductive inference. Tech. Rep. 19-98, Knowledge Systems Laboratory, Stanford University, Stanford, Calif.
• 41: NAYAK, A., 1994. Iterated belief change based on epistemic entrenchment. Erkenntnis 41, 353-390.
• 42: Abhaya C. Nayak , Norman Y. Foo, Reasoning without Minimality, Proceedings of the 5th Pacific Rim International Conference on Artificial Intelligence: Topics in Artificial Intelligence, p.122-133, November 22-27, 1998
• 43: NTAFOS, S., AND HAKIMI, S. 1979. On path cover problems in digraphs and applications to program testing. IEEE Tran. Softw. Eng. SE-5, 520-529.
• 44: PENG,Y.,AND REGGIA, J. 1986. Plausibility of diagnostic hypothesis. In Proceedings of the 5th National Conference on Artificial Intelligence. AAAI/MIT Press, Menlo Park, Calif., pp., 140-145.
• 45: N. S. V. Rao, Computational Complexity Issues in Operative Diagnostics of Graph-Based Systems, IEEE Transactions on Computers, v.42 n.4, p.447-457, April 1993 [doi>10.1109/12.214691]
• 46: Bart Selman , Henry Kautz, Knowledge compilation and theory approximation, Journal of the ACM (JACM), v.43 n.2, p.193-224, March 1996 [doi>10.1145/226643.226644]
• 47: SELMAN, B., AND LEVESQUE, H. J. 1990. Abductive and default reasoning: A computational core. In Proceedings of the 8th National Conference on Artificial Intelligence. AAAI/MIT Press, Menlo Park, Calif., pp. 343-348.
• 48: SPOHN, W. 1988. Ordinal conditional functions: A dynamic theory of epistemic states. In Causation in Decision; Belief Change; and Statistics. Kluwer Academics, Dordrecht, The Netherlands, pp. 105-134.
• 49: TADEPALLI,P.,AND NATARAJAN, B. 1996. A formal framework for speedup learning from problems and solutions. J. Artif. Int. Res. 4, 445-475.
• 50: Peter van Beek , Rina Dechter, Constraint tightness and looseness versus local and global consistency, Journal of the ACM (JACM), v.44 n.4, p.549-566, July 1997 [doi>10.1145/263867.263499]
• 51: S. Venkatesan , K. V. S. Ramarao, Computing associative functions distributively in spite of link failures, Journal of Parallel and Distributed Computing, v.23 n.3, p.399-410, Dec. 1994 [doi>10.1006/jpdc.1994.1149]
• 52: WILLIAMS, M. 1994. Transmutations of knowledge systems. In Proceedings of the 4th International Conference on the Principles of Knowledge Representation and Reasoning. Morgan-Kaufmann, San Mateo, Calif., pp. 619-629.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Theory

Keywords:
Compilability, preprocessing