Jump to ContentJump to Main Navigation
Computational Complexity and Statistical Physics$
Users without a subscription are not able to see the full content.

Allon Percus, Gabriel Istrate, and Cristopher Moore

Print publication date: 2005

Print ISBN-13: 9780195177374

Published to Oxford Scholarship Online: November 2020

DOI: 10.1093/oso/9780195177374.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (oxford.universitypressscholarship.com). (c) Copyright Oxford University Press, 2021. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. date: 05 March 2021

Towards a Predictive Computational Complexity Theory for Periodically Specified Problems: A Survey

Towards a Predictive Computational Complexity Theory for Periodically Specified Problems: A Survey

Chapter 13 Towards a Predictive Computational Complexity Theory for Periodically Specified Problems: A Survey
Computational Complexity and Statistical Physics

Harry B. Hunt III

Madhav V. Marathe

Oxford University Press

The preceding chapters in this volume have documented the substantial recent progress towards understanding the complexity of randomly specified combinatorial problems. This improved understanding has been obtained by combining concepts and ideas from theoretical computer science and discrete mathematics with those developed in statistical mechanics. Techniques such as the cavity method and the replica method, primarily developed by the statistical mechanics community to understand physical phenomena, have yielded important insights into the intrinsic difficulty of solving combinatorial problems when instances are chosen randomly. These insights have ultimately led to the development of efficient algorithms for some of the problems. A potential weakness of these results is their reliance on random instances. Although the typical probability distributions used on the set of instances make the mathematical results tractable, such instances do not, in general, capture the realistic instances that arise in practice. This is because practical applications of graph theory and combinatorial optimization in CAD systems, mechanical engineering, VLSI design, transportation networks, and software engineering involve processing large but regular objects constructed in a systematic manner from smaller and more manageable components. Consequently, the resulting graphs or logical formulas have a regular structure, and are defined systematically in terms of smaller graphs or formulas. It is not unusual for computer scientists and physicists interested in worst-case complexity to study problem instances with regular structure, such as lattice-like or tree-like instances. Motivated by this, we discuss periodic specifications as a method for specifying regular instances. Extensions of the basic formalism that give rise to locally random but globally structured instances are also discussed. These instances provide one method of producing random instances that might capture the structured aspect of practical instances. The specifications also yield methods for constructing hard instances of satisfiability and various graph theoretic problems, important for testing the computational efficiency of algorithms that solve such problems. Periodic specifications are a mechanism for succinctly specifying combinatorial objects with highly regular repetitive substructure. In the past, researchers have also used the term dynamic to refer to such objects specified using periodic specifications (see, for example, Orlin [419], Cohen and Megiddo [103], Kosaraju and Sullivan [347], and Hoppe and Tardos [260]).

Keywords:   algebraic morphisms, cellular automata, decision problems, easiness results, finite conjunctions, literals, local transformations, network scheduling, parallel programming

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .