15125535
The Hardest Random SAT Problems
We describe a detailed experimental investigation of the phase transition for several different classes of satisfiability problems including random k-SAT, the constant probability model, and encodings of k-colourability and the independent set problem. We show that the constant probability model has been prematurely dismissed in favour of the random k-SAT model. We also show that for each of these problem class the conventional picture of easy-hard-easy behaviour is inadequate. In each of the problem classes, although median problem difficulty shows an easy-hard-easy pattern, there is also a region of very variable problem difficulty. Within this region, we have found problems orders of magnitude harder than those in the middle of the phase transition. These extraordinary problems can easily dominate the mean problem difficulty. We report experimental evidence which strongly suggests that this behaviour is due to a “constraint gap”, a region where the number of constraints on variables is minimal while simultaneously the depth of search required to solve problems is maximal. We also report results suggesting that better algorithms will be unable to eliminate this constraint gap and hence will continue to find very difficult problems in this region. Finally, we report an interesting correlation between these variable regions and a peak in the number of prime implicates. We predict that these extraordinarily hard problems will be of considerable use in analysing and comparing the performance of satisfiability algorithms.
17485829
Beyond Finite Domains: The All Different and Global Cardinality Constraints
We describe how the propagator for the ALL-DIFFERENT constraint can be generalized to prune variables whose domains are not just simple finite integer domains. We show, for example, how it can be used to propagate set, multiset and tuple variables.
8350620
The Use of Proof Plans to Sum Series
We describe a program for finding closed form solutions to finite sums. The program was built to test the applicability of the proof planning search control technique in a domain of mathematics outwith induction. This experiment was successful. The series summing program extends previous work in this area and was built in a short time just by providing new series summing methods to our existing inductive theorem proving system CLAM.
2156641
Multiset Ordering Constraints
We identify a new and important global (or nonbinary) constraint which ensures that the values taken by two vectors of variables, when viewed as multisets, are ordered. This constraint is useful for a number of different applications including breaking symmetry and fuzzy constraint satisfaction. We propose and implement a linear time algorithm for enforcing generalised arc-consistency on such a multiset ordering constraint. Experimental results show considerable promise.
11070611
The Constrainedness of Arc Consistency
We show that the same methodology used to study phase transition behaviour in NP-complete problems works with a polynomial problem class: establishing arc consistency. A general measure of the constrainedness of an ensemble of problems, used to locate phase transitions in random NP-complete problems, predicts the location of a phase transition in establishing arc consistency. A complexity peak for the AC3 algorithm is associated with this transition. Finite size scaling models both the scaling of this transition and the computational cost. On problems at the phase transition, this model of computational cost agrees with the theoretical worst case. As with NP-complete problems, constrainedness — and proxies for it which are cheaper to compute — can be used as a heuristic for reducing the number of checks needed to establish arc consistency in AC3. 
 
The authors are supported by EPSRC awards GR/L/24014 and GR/K/65706, and the EU award EU20603. The authors wish to thank other members of the APES research group for their help, and Gene Freuder.
5055655
The Complexity of Global Constraints
We study the computational complexity of reasoning with global constraints. We show that reasoning with such constraints is intractable in general. We then demonstrate how the same tools of computational complexity can be used in the design and analysis of specific global constraints. In particular, we illustrate how computational complexity can be used to determine when a lesser level of local consistency should be enforced, when decomposing constraints will lose pruning, and when combining constraints is tractable. We also show how the same tools can be used to study symmetry breaking, meta-constraints like the cardinality constraint, and learning nogoods.
3106079
Efficient Exploration With Latent Structure
When interacting with a new environment, a robot can improve its online performance by efficiently exploring the effects of its actions. The efficiency of exploration can be expanded significantly by modeling and using latent structure to generalize experiences. We provide a theoretical development of the problem of exploration with latent structure, analyze several algorithms and prove matching lower bounds. We demonstrate our algorithmic ideas on a simple robot car repeatedly traversing a path with two different surface properties.
17164164
Towards Measuring Similarity in Description Logics
We review several kinds of previously studied concept similarity measures, and then rephrase them in terms of a simple DL. We discuss the difficulties encountered in trying to generalize these formulations to more complex DLs, and settle on one based on probability/information theory as being the most principled. 1 Motivation and Goals The idea of measuring concept similarity has received considerable attention in several domains, including psychology, cognitive science, and computational linguistics and information retrieval. This work has been applied and extended recently in the field of Information Integration, which often relies on ontologies and hence concepts described in DLs. Most past work has concentrated on the similarity of “atomic” concepts (word senses), rather than composite, defined concepts, which are the stock-in-trade of DLs. This has sometimes been characterized as the difference between considering nouns appearing in a dictionary, e.g. WordNet, and general arbitrary noun phrases. The modest goal of this paper is to consider the problem of generalizing previous efforts to define similarity for primitive concepts to composite ones. To this end, we review three classes of approaches found in the current literature, rephrase them in terms of a very simple description logic, and then try to generalize this to a complex DL. These extensions invite a host of new questions that we leave open for further research. To begin with, we make several observations about possible real-valued function(s) sim(C,D) that would measure concept similarity in general. First, any effort to assess simlarity via absolute numeric values seems ill-advised — in small experiments even human judgments have been shown to correlate only in the .91 to .94 range. A less exacting target is to use sim to provide relative orderings over concepts. Some researchers have studied a complementary measure, distance dist(C,D), which can similarly be used for ordering alternatives. To the extent that two functions provide similar orderings (e.g., consistently differing by a constant factor) they are essentially indistinguishable for our purposes. Nonetheless, there are two important general properties that are widely agreed to be desirable for sim(C,D): 1. sim(C,D) is positively correlated with the amount of commonality between C and D. 2. sim(C,D) is negatively correlated with the amount of difference between C and D. The key question then becomes how to measure “commonality”; in turn, this is related to how information about the concept is captured. 2 Three approaches to concept similarity Clearly, in order to compare concepts we need to consider what information we have available about them. We follow Rodriguez [14] in categorizing a variety of approaches, and for each we give a few of the best known functions, which we shall follow. Feature-based Models In this approach, a concept C is characterized by a a set of features ftrs(C). In his pioneering work on similarity, the psychologist Amos Tversky [16] introduced two families of measures: the “contrast model”, where the similarity of C and D is a linear function: contrasttv(C,D) = θf(ftrs(C) ∩ ftrs(D)) − αf(ftrs(C) \ ftrs(D))− βf(ftrs(D) \ ftrs(C)), where \ is set difference, θ, α, and β are non-negative constants, and where f(.) is often taken as the count of features in the set (written |.|). Tversky also proposed a normalized “ratio model”, where similarity is a fraction involving these sets:
43061363
Counting labelled three-connected and homeomorphically irreducible two-connected graphs
Abstract Recursive procedures are obtained for counting isomorphism classes of three-connected graphs and of two-connected graphs without vertices of degree 2. We apply an enumeration tool developed by R. W. Robinson to count non-isomorphic 2-connected graphs: he expressed the sums of cycle indices of automorphism groups of connected graphs in terms of those of their 2-connected components, and we do the same for 2-connected graphs and their 3-connected components.
8458935
Efficient enumeration of sensed planar maps
We use Liskovets' quotient maps and Robinson's cycle index sums to count 1-, 2- and 3-connected planar maps by number of vertices and edges up to sense-preserving homeomorphism of the embedding sphere. Although Wormald has already counted these maps up to all homeomorphism, sense-reversing as well as sense-preserving, our methods are computationally more efficient for counting these maps up to orientation-preserving homeomorphism and yield closed-form enumeration formulas in the case of 1- and 2-connected maps. Our formula for 1-connected planar maps uses the number of rooted planar maps with i+1 vertices and j+1 faces; we evaluate these numbers using a method that is more efficient than substituting into Tutte's parametric equations, and we also count rooted toroidal maps by number of vertices and faces more efficiently than by substituting into Arques' explicit formula.
18489826
Counting unrooted loopless planar maps
We present a formula for the number of n-edge unrooted loopless planar maps considered up to orientation-preserving isomorphism. The only sum contained in this formula is over the divisors of n.