Search Results

This chapter discusses three introductory examples for studying exact and fixed-parameter algorithms. It starts with the boolean Satisfiability problem and its numerous parameters, then discusses an application problem from railway optimization, and concludes with a communication problem in tree networks (Multicut in Trees). It briefly summarizes the leitmotif of parameterized algorithm design and analysis.

Because of Cook's theorem, satisfiability lies at the heart of computational complexity theory. This chapter presents some selected research directions, focusing on ensembles of random satisfiability instances. When the density of constraints is increased, a phase transition between a SAT and an UNSAT phase take place. Properly tuned ensembles with a density close to the transition point provide a generator of particularly hard instances. The nature of this transition is discussed, and bounds on the critical density are obtained. On the algorithmic side, the discussion focuses on exhaustive search algorithms based on tree-search, and on random walk procedures.

In graphical models whose factor graph has a locally tree-like structure, belief propagation may fail because variables become correlated at large distances. This phenomenon has been observed in many problems, from satisfiability to colouring or error correcting codes. This chapter describes a physics-based approach for dealing with such a problem, the ‘one step replica symmetry breaking’ (1RSB) cavity method. It is based on the idea of counting solutions to belief propagation equations, and has strong connections with the theory of pure states decomposition. Its algorithmic side, the survey propagation algorithm, is motivated and described in details. The general theory is illustrated through its application to the XORSAT problem studied in Chapter 18.

This chapter studies an ensemble of random satisfiability problems, ‘random K-satisfiability’ (K-SAT). Applying the 1RSB cavity method, it first derives the phase diagram in the limit of large N, in particular the location of the SAT-UNSAT threshold. Within the SAT phase, the chapter focuses on the intermediate clustered phase close, and computes the number of clusters to leading exponential order in N. The application of survey propagation to this problem is then described. Combined with a simple decimation procedure, the chapter provides an efficient method for finding satisfiable assignments in the clustered phase. The whole chapter is based on heuristic arguments. There is not yet any rigorous proof of the results presented, neither concerning the phase diagram, nor the convergence properties of message passing algorithms and their use in decimation procedures.

This chapter provides an elementary introduction to some basic concepts in theoretical computer science. It includes basic notions of graph theory and an informal introduction to computational complexity, presenting the basic classes P, NP, and NP-complete. These notions are illustrated by discussions of the minimal spanning tree and satisfiability problems, and by applications from statistical physics (spin glasses and maximum cuts), and from coding theory (decoding complexity).

A decision-making problem is often formulated as the minimization or maximization of a multivariable function, an optimization problem. This chapter shows that the methods of statistical mechanics are useful to study some types of optimization problems including the number partitioning, the graph partitioning, the knapsack problem, and the satisfiability problem. All these problems are shown to be formulated and solved using the theory of spin glasses, in particular the replica method. Then, discussions are continued on the mathematical properties of simulated annealing, an approximate numerical method for generic optimization problems.

In Conway’s Game of Life [2], if one starts with a large array of randomly set cells, then after around twenty thousand generations one will see that all motion has died down, and only stationary objects of low period remain, providing a final density of about .0287. No methods are known for proving rigorously that this behavior should occur, but it is reliably observed in simulations. This brings up several interesting related questions. Why does this “freezing” occur? After everything has frozen, what is the remaining debris composed of? Is there some construction that can “eat through” the debris? If we start with an infinitely large random grid, so that all constructions appear somewhere, what will the long term behavior be? It seems clear that knowing the composition of typical debris is central to many such questions. Much effort has gone into analyzing the objects that occur in such stationary debris, as well as into determining what stationary objects can exist at all in Life [4, 8], Both of these endeavors depend on having some notion of what an “object” is in the first place. One simple notion is that of an island, a maximal set of live cells connected to each other by paths of purely live cells. But many common objects, such as the “aircraft carrier,” are not connected so strongly. They are composed of more than one island, but we think of them as a single object anyway, since their constituent islands are not separately stable. Any pattern that is stable (has period one, i.e., does not change over time) is called a still life. Since a collection of stable objects can satisfy this definition, the term strict still life is used to refer to a single indivisible stable object, and pseudo still life is used to refer to a stable pattern that is composed of distinct strict still lifes. For example, the bi-block is a pseudo still life, since it is composed of two blocks, but the aircraft carrier is a strict still life, since its islands are not stable on their own.

This chapter argues for the opting-for-the-best view: the view that, for any subject S and any member ϕ‎ of a certain subset of S’s options, S ought to ϕ‎ if and only if ϕ‎ is the best member of this subset in terms of whatever ultimately matters. It’s argued that we need to restrict ourselves to a subset of the subject’s options because of the problem of act versions. This problem arises in the following sort of case. One’s best option is to kiss one’s partner passionately. Kissing her nonpassionately would be disastrous. Indeed, it would be better not to kiss her at all. But, unfortunately, if you were to kiss her, you would do so nonpassionately. Should you kiss her? Of course, you have to kiss her to kiss her passionately, which is your best option. But kissing her would result in your kissing her nonpassionately, which is your worst option.