The Physical View of Computational Complexity

Dr. Allon Percus
Division of Computer, Computational and Statistical Sciences, LANL / Department of Mathematics, UCLAPhysicists define a phase transition as an abrupt change in microscopic order, such as the transition from a solid to a liquid. Many fundamental problems in computer science exhibit phase transitions as well. The classic example is satisfiability: given a set of logical constraints acting on Boolean variables, can one assign truth values to the variables so that all constraints are simultaneously satisfied? For randomly generated formulas with many variables, as one increases the number of constraints per variable, there is a threshold at which the answer goes abruptly from almost certainly yes to almost certainly no. Moreover, this phase transition is connected with algorithmic performance. Over a wide range of computational problems, the hardest instances to solve are those near the transition. I will discuss the role of phase transitions in random combinatorial problems,demonstrating how the physical view of the phase structure has transformed our understanding of average-case computational complexity and inspired new algorithmic approaches.

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Shane Goodoff