Catálogo de publicaciones - libros

The input to a constraint satisfaction problem (CSP) consists of a set of variables, each with a domain, and constraints between these variables formulated by relations over the appropriate domains; the question is if there is an assignment of values to the variables that satisfies all constraints. Different algorithmic tasks for CSPs (checking satisfiability, counting the number of solutions, enumerating all solutions) can be used to model many problems in areas such as computational logic, artificial intelligence, circuit design, etc. We will survey results on the complexity of these computational tasks as a function of properties of the allowed constraint relations. Particular attention is paid to the special case of Boolean constraint relations.

As one simple type of statistical inference problems we consider , a task of finding a most likely solution (MLS in short) for a given problem instance under some given probability model. Although many MLS problems are NP-hard, we propose, for these problems, to study their average-case complexity under their assumed probabality models. We show three examples of MLS problems, and explain that “message passing algorithms” (e.g., belief propagation) work reasonably well for these problems. Some of the technical results of this paper are from the author’s recent joint work with his colleagues [WST, WY06, OW06] .

The intention of this talk is to look at various models of transfinite computation and give some calculations as to their comparative power. To clarify the kind of models that we are looking at, they will all be acting: this will mean that they essentially perform simple discrete tasks in simple steps or stages. The reader should have in mind the paradigm of the which of course performs such simple actions as moving one cell left or right on the tape that it is reading, altering a symbol, changing a state . We are thus not considering any kind of machine or notional device that computes in an analogue fashion, nor any machine, such as neural network with nodes primed by infinitely precise real numbers, nor computations performed in chemistry beakers, across cell membranes, or in buckets of slime.

Amorphous computing differs from the classical ideas about computations almost in every aspect. The architecture of amorphous computers is random, since they consist of a plethora of identical computational units spread randomly over a given area. Within a limited radius the units can communicate wirelessly with their neighbors via a single-channel radio. We consider a model whose assumptions on the underlying computing and communication abilities are among the weakest possible: all computational units are finite state probabilistic automata working asynchronously, there is no broadcasting collision detection mechanism and no network addresses. We show that under reasonable probabilistic assumptions non-uniform families of such amorphous computers can possess universal computing power with a high probability. To the best of our knowledge this is the first result showing the universality of such computing systems.

We survey some work concerned with small universal Turing machines, cellular automata, and other simple models of computation. For example it has been an open question for some time as to whether the smallest known universal Turing machines of Minsky, Rogozhin, Baiocchi and Kudlek are efficient (polynomial time) simulators of Turing machines. These are some of the most intuitively simple computational devices and previously the best known simulations were exponentially slow. We discuss recent work that shows that these machines are indeed efficient simulators. As a related result we also find that Rule 110, a well-known elementary cellular automaton, is also efficiently universal. We also mention some new universal program-size results, including new small universal Turing machines and new semi-weakly universal Turing machines. We then discuss some ideas for future work arising out of these, and other, results.

Given a tree with costs on edges and a collection of terminal sets  = {, , ..., }, the generalized Multicut problem asks to find a set of edges on whose removal cuts every terminal set in , such that the total cost of the edges is minimized. The standard version of the problem can be approximately solved by reducing it to the classical Multicut on trees problem. For the prize-collecting version of the problem, we give a primal-dual 3-approximation algorithm and a randomized 2.55-approximation algorithm (the latter can be derandomized). For the -version of the problem, we show an interesting relation between the problem and the Densest -Subgraph problem, implying that approximating the -version of the problem within () for some small > 0 is hard. We also give a min { 2( −  + 1), }-approximation algorithm for the -version of the problem via a nonuniform approach.

We survey and compare models of computation on real numbers exceeding the Church–Turing Hypothesis.