article

Phase transitions and the search problem

Authors:

Tad Hogg,

Bernardo A. Huberman,

Colin P. WilliamsAuthors Info & Claims

Artificial Intelligence, Volume 81, Issue 1-2

Pages 1 - 15

https://doi.org/10.1016/0004-3702(95)00044-5

Published: 01 March 1996 Publication History

Abstract

No abstract available.

Cited By

View all

Nájera VOrtega JCollazos Morales CRoblero Aguilar S(2023)From Selecting Best Algorithm to Explaining Why It is: A General Review, Formal Problem Statement and Guidelines Towards to an Empirical GeneralizationComputational Science and Its Applications – ICCSA 202310.1007/978-3-031-36805-9_45(694-712)Online publication date: 3-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-36805-9_45
Krarup BKrivic SMagazzeni DLong DCashmore MSmith D(2022)Contrastive Explanations of Plans through Model RestrictionsJournal of Artificial Intelligence Research10.1613/jair.1.1281372(533-612)Online publication date: 4-Jan-2022
https://dl.acm.org/doi/10.1613/jair.1.12813
Paparrizou AWattez H(2020)Perturbing Branching Heuristics in Constraint SolvingPrinciples and Practice of Constraint Programming10.1007/978-3-030-58475-7_29(496-513)Online publication date: 7-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-58475-7_29
Show More Cited By

Index Terms

Phase transitions and the search problem
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

Local search and the number of solutions
CP'96: Proceedings of the 2nd International Conference on Principles and Practice of Constraint Programming

There has been considerable research interest into the solubility phase transition, and its effect on search cost for backtracking algorithms. In this paper we show that a similar easy-hard-easy pattern occurs for local search, with search cost peaking ...
Many hard examples in exact phase transitions

This paper analyzes the resolution complexity of two random constraint satisfaction problem (CSP) models (i.e. Model RB/RD) for which we can establish the existence of phase transitions and identify the threshold points exactly. By encoding CSPs into ...
Saving Support-Checks Does Not Always Save Time

Arc-consistency algorithms are the workhorse of backtrackers that maintain arc-consistency (MAC). This paper will provide experimental evidence that, despite common belief to the contrary, it is not always necessary for a good arc-consistency algorithm ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Artificial Intelligence Volume 81, Issue 1-2

Special volume on frontiers in problem solving: phase transitions and complexity

March 1996

55 pages

ISSN:0004-3702

Editors:
Daniel G. Bobrow
Xerox Palo Alto Research Center, Palo Alto, CA
,
Tad Hogg
Xerox Palo Alto Research Center, Palo Alto, CA
,
Bernardo A. Huberman
Xerox Palo Alto Research Center, Palo Alto, CA
,
Colin P. Williams
Stanford Univ., Stanford, CA

Issue’s Table of Contents

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 March 1996

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

62
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Nájera VOrtega JCollazos Morales CRoblero Aguilar S(2023)From Selecting Best Algorithm to Explaining Why It is: A General Review, Formal Problem Statement and Guidelines Towards to an Empirical GeneralizationComputational Science and Its Applications – ICCSA 202310.1007/978-3-031-36805-9_45(694-712)Online publication date: 3-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-36805-9_45
Krarup BKrivic SMagazzeni DLong DCashmore MSmith D(2022)Contrastive Explanations of Plans through Model RestrictionsJournal of Artificial Intelligence Research10.1613/jair.1.1281372(533-612)Online publication date: 4-Jan-2022
https://dl.acm.org/doi/10.1613/jair.1.12813
Paparrizou AWattez H(2020)Perturbing Branching Heuristics in Constraint SolvingPrinciples and Practice of Constraint Programming10.1007/978-3-030-58475-7_29(496-513)Online publication date: 7-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-58475-7_29
Mann Z(2018)Complexity of Coloring Random GraphsACM Journal of Experimental Algorithmics10.1145/318335023(1-19)Online publication date: 22-Mar-2018
https://dl.acm.org/doi/10.1145/3183350
Dickerson JKazachkov AProcaccia ASandholm TSingh SMarkovitch S(2017)Small representations of big kidney exchange graphsProceedings of the Thirty-First AAAI Conference on Artificial Intelligence10.5555/3298239.3298312(487-493)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3298239.3298312
Gent IJefferson CNightingale P(2017)Complexity of n-queens completionJournal of Artificial Intelligence Research10.5555/3176788.317680759:1(815-848)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.5555/3176788.3176807
Elser V(2017)Matrix product constraints by projection methodsJournal of Global Optimization10.1007/s10898-016-0466-968:2(329-355)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1007/s10898-016-0466-9
Chen ZHe ZHe C(2017)An improved DPOP algorithm based on breadth first search pseudo-tree for distributed constraint optimizationApplied Intelligence10.1007/s10489-017-0905-447:3(607-623)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1007/s10489-017-0905-4
Okimoto TSchwind NClement MRibeiro TInoue KMarquis PWeiss GYolum PBordini RElkind E(2015)How to Form a Task-Oriented Robust TeamProceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems10.5555/2772879.2772931(395-403)Online publication date: 4-May-2015
https://dl.acm.org/doi/10.5555/2772879.2772931
Nicosia GConca P(2015)Characterization of the #k---SAT Problem in Terms of Connected ComponentsRevised Selected Papers of the First International Workshop on Machine Learning, Optimization, and Big Data - Volume 943210.1007/978-3-319-27926-8_23(257-268)Online publication date: 21-Jul-2015
https://dl.acm.org/doi/10.1007/978-3-319-27926-8_23
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Index Terms

Recommendations

Local search and the number of solutions

Many hard examples in exact phase transitions

Saving Support-Checks Does Not Always Save Time

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations