The very particular structure of the very hard instances
National Conference on Artificial IntelligencePublished 4 August 1996
Dan R. Vlasie
Citations8
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that the algorithms which behave well on average may have difficulty only for highly structured, non-random inputs, except in a finite number of cases.
Abstract
We show that the algorithms which behave well on average may have difficulty only for highly structured, non-random inputs, except in a finite number of cases. The formal framework is provided by the theory of Kolmogorov complexity. An experimental verification is done for graph 3-colorability with Brelaz's algorithm.
Keywords
Computer Science
Communications of the ACMNew methods to color the vertices of a graph
1,564 Citations1979Daniel Brélaz
An exact method is given which performs better than the Randall-Brown algorithm and is able to color larger graphs and the new heuristic methods, the classical methods, and the exact method are compared.
Where the really hard problems are
1,021 Citations1991Peter Cheeseman, Bob Kanefsky +1 more
It is shown that NP-complete problems can be summarized by at least one "order parameter", and that the hard problems occur at a critical value of such a parameter.
Artificial IntelligenceMinimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems
830 Citations1992Steven Minton, Mark Johnston +2 more
A theoretical analysis is presented both to explain why this heuristic approach to solving large-scale constraint satisfaction and scheduling problems works well on certain types of problems and to predict when it is likely to be most effective.
National Conference on Artificial IntelligenceHard and easy distributions of SAT problems
801 Citations1992David G. M. Mitchell, Bart Selman +1 more
It is shown that by using the right distribution of instances, and appropriate parameter values, it is possible to generate random formulas that are hard, that is, for which satisfiability testing is quite difficult.
ACM SIGACT NewsBook Review: An introduction to Kolmogorov Complexity and its Applications Second Edition, 1997 by Ming Li and Paul Vitanyi (Springer (Graduate Text Series))
585 Citations1997William Gasarch
The complexity of a string is defined as the shortest description of x, and a formal definition is given that is equivalent to the one in the book.
SIAM Journal on ComputingAverage Case Complete Problems
425 Citations1986Leonid A. Levin
It is shown in [1] that the Tiling problem with uniform distribution of instances has no polynominal “on average” algorithm, unless every NP-problem with every simple probability distribution has it.
Information and Randomness: An Algorithmic Perspective
316 Citations1994Cristian S. Calude
Experimental results on the crossover point in satisfiability problems
210 Citations1993James M. Crawford, Larry D. Auton
Empirically, it is found that for random 3-SAT problems below the crossover point, the average time complexity of satisfiability problems seems empirically to grow linearly with problem size, and at and above therossover point the complexity seems to grow exponentially, but the rate of growth seems to be greatest near the crossoverpoint.
Journal of AlgorithmsAlmost all k-colorable graphs are easy to color
165 Citations1988Jonathan Turner
A simple and efficient heuristic algorithm for the graph coloring problem is described and it is shown that for all k ≥ 1, it finds an optimal coloring for almost all k -colorable graphs.
Artificial IntelligenceThe hardest constraint problems: A double phase transition
134 Citations1994Tad Hogg, Colin P. Williams
The distribution of hard graph coloring problems as a function of graph connectivity is shown to have two distinct transition behaviors, including a peak in the median search cost near the connectivity at which half the graphs have solutions.
Artificial IntelligenceExploiting the deep structure of constraint problems
123 Citations1994Colin P. Williams, Tad Hogg
A technique for analyzing the behavior of sophisticated AI search programs working on realistic, large-scale problems is introduced and it is suggested that this type of analysis can be generalized to other kinds of AI problems.
Information Processing LettersAverage time analysis of simplified Davis-Putnam procedures
92 Citations1982Allen J. Goldberg, Paul W. Purdom +1 more
Information Processing LettersOn the greedy algorithm for satisfiability
90 Citations1992Ηλίας Κουτσουπιάς, Christos H. Papadimitriou
It is shown that for the vast majority of satisfiable 3CNF formulae, the local search heuristic that starts at a random truth assignment and repeatedly flips the variable that improves the number of satisfied clauses the most, almost always succeeds in discovering a satisfying truth assignment.
Using deep structure to locate hard problems
70 Citations1992Colin P. Williams, Tad Hogg
This paper shows how to predict where, in a space of problem instances, the hardest problems are to be found and where the fluctuations in difficulty are greatest.
Information Processing LettersAverage case complexity under the universal distribution equals worst-case complexity
58 Citations1992Ming Li, Paul Vitányi
The average complexity of any algorithm whatsoever under the universal distribution is of the same order of magnitude as the worst-case complexity for time complexity and for space complexity.
How long will it take
23 Citations1992Ron Musick, Stuart Russell
A method for approximating the expected number of steps required by a heuristic search algorithm to reach a goal from any initial state in a problem space is presented, based on a mapping from the original state space to an abstract space in which states are characterized only by a syntactic "distance" from the nearest goal.
Systematic generation of very hard cases for graph 3-colorability
20 Citations2002R.D. Vlasie
A simple generation procedure is presented which turns out to be an effective source of very hard cases for graph 3-colorability, and the graphs distributed according to this generation procedure are much denser in veryhard cases than previously reported for the same problem size.
Lecture notes in computer scienceCombining hill climbing and forward checking for handling disjunctive constraints
1 Citations1995Dan R. Vlasie
A simple search method is described which ameliorates the standard forward checking by a preliminary hillclimbing step and applies this method to solve a combinatorial search problem: checking the consistency of disjunctive constraint sets.