Abstraction and Phase Transitions

摘要: Abstraction and Phase Transitions Lorenza Saitta* Jean-Daniel Zucker + * Universita del Piemonte OrientaleDipartimento di Scienze e Tecnologie AvanzateCorso Borsalino 5415100 Alessandria (Italy)saitta@di.unito.it Universite Paris VI - CNRSLaboratoire d’Informatique de 64, Place JussieuF-75252 (France)Jean-Daniel.Zucker@lip6.fr 1.Introduction Computational complexity is often a major obstacle to the application of AI techniques tosignificant real-world problems. Efforts are then required understand sources thiscomplexity, in order tame it without introducing, if possible, too strong simplifications that makeeither problem or technique useless.It has been well known since early times representation key issue facilitatesolving [Newel & Simon, 72; Sacerdoti, 73; Amarel,83; Korf, 80; Ellman, 1993; Holte etal., 1996; Chouery et al., 98], even though there clearly no hope turning, by representationchange, an intractable class problems into tractable one. However, computationalcharacterization classes based on worst-case analysis, and, hence, not every probleminstance equally hard solve [Cheeseman al. 1991].On other hand, recent investigations have uncovered common structure, inside ofproblems, characterizing finding solutions. In fact, several ofcomputationally difficult problems, such as K-Satisfiability (K-SAT), Constraint Satisfaction(CSP), graph K-coloring [Hogg, 1996], decision version Traveling Salespersonproblems show