
Contents
-
-
-
-
-
-
-
-
-
-
-
-
-
-
1 Introduction 1 Introduction
-
2 Motivation 2 Motivation
-
3 Preliminary Definitions 3 Preliminary Definitions
-
3.1 Periodically Specified Graphs 3.1 Periodically Specified Graphs
-
3.2 Types Of Periodic Specifications 3.2 Types Of Periodic Specifications
-
-
4 Extension Of The Basic Formalism 4 Extension Of The Basic Formalism
-
4.1 Periodically Specified Constraint Satisfaction Problems 4.1 Periodically Specified Constraint Satisfaction Problems
-
4.2 Rules For Constructing Expanded Graphs 4.2 Rules For Constructing Expanded Graphs
-
4.3 Semantics Of Satisfaction 4.3 Semantics Of Satisfaction
-
4.4 Periodically Specified Quantified Formulas 4.4 Periodically Specified Quantified Formulas
-
-
5 Techniques: Hardness And Easiness Results 5 Techniques: Hardness And Easiness Results
-
5.1 Local Transformations 5.1 Local Transformations
-
5.2 Relational Representability 5.2 Relational Representability
-
5.3 Simultaneous Reductions Based On Local Transformations 5.3 Simultaneous Reductions Based On Local Transformations
-
5.4 Putting It All Together: Lifting Of Simultaneous Reductions Based On Local Transformations 5.4 Putting It All Together: Lifting Of Simultaneous Reductions Based On Local Transformations
-
-
6 Techniques: Easiness Result 6 Techniques: Easiness Result
-
6.1 Polynomial Time Algorithms 6.1 Polynomial Time Algorithms
-
6.2 Approximation Algorithms 6.2 Approximation Algorithms
-
-
7 Complexity Theoretic Insights 7 Complexity Theoretic Insights
-
7.1 Predictive Complexity Theory 7.1 Predictive Complexity Theory
-
7.2 Natural Morphisms For Computational Complexity 7.2 Natural Morphisms For Computational Complexity
-
-
8 Periodic Satisfiability Forever 8 Periodic Satisfiability Forever
-
9 Conclusions And Future Work 9 Conclusions And Future Work
-
9.1 Periodically Specified Random Constraint Satisfaction Problems 9.1 Periodically Specified Random Constraint Satisfaction Problems
-
9.2 Lattice-Like Instances For Satisfiability Problems 9.2 Lattice-Like Instances For Satisfiability Problems
-
-
Acknowledgments Acknowledgments
-
-
-
-
13 Towards a Predictive Computational Complexity Theory for Periodically Specified Problems: A Survey
Get access-
Published:December 2005
Cite
Abstract
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]).
Sign in
Personal account
- Sign in with email/username & password
- Get email alerts
- Save searches
- Purchase content
- Activate your purchase/trial code
- Add your ORCID iD
Purchase
Our books are available by subscription or purchase to libraries and institutions.
Purchasing informationMonth: | Total Views: |
---|---|
October 2022 | 1 |
February 2023 | 2 |
March 2023 | 1 |
June 2023 | 1 |
June 2024 | 2 |
November 2024 | 2 |
January 2025 | 2 |
Get help with access
Institutional access
Access to content on Oxford Academic is often provided through institutional subscriptions and purchases. If you are a member of an institution with an active account, you may be able to access content in one of the following ways:
IP based access
Typically, access is provided across an institutional network to a range of IP addresses. This authentication occurs automatically, and it is not possible to sign out of an IP authenticated account.
Sign in through your institution
Choose this option to get remote access when outside your institution. Shibboleth/Open Athens technology is used to provide single sign-on between your institution’s website and Oxford Academic.
If your institution is not listed or you cannot sign in to your institution’s website, please contact your librarian or administrator.
Sign in with a library card
Enter your library card number to sign in. If you cannot sign in, please contact your librarian.
Society Members
Society member access to a journal is achieved in one of the following ways:
Sign in through society site
Many societies offer single sign-on between the society website and Oxford Academic. If you see ‘Sign in through society site’ in the sign in pane within a journal:
If you do not have a society account or have forgotten your username or password, please contact your society.
Sign in using a personal account
Some societies use Oxford Academic personal accounts to provide access to their members. See below.
Personal account
A personal account can be used to get email alerts, save searches, purchase content, and activate subscriptions.
Some societies use Oxford Academic personal accounts to provide access to their members.
Viewing your signed in accounts
Click the account icon in the top right to:
Signed in but can't access content
Oxford Academic is home to a wide variety of products. The institutional subscription may not cover the content that you are trying to access. If you believe you should have access to that content, please contact your librarian.
Institutional account management
For librarians and administrators, your personal account also provides access to institutional account management. Here you will find options to view and activate subscriptions, manage institutional settings and access options, access usage statistics, and more.