Events

The talk discusses a framework enabling one to define and determine the complexity of various universal programs U for various machines. The approach consists of first defining the complexity as the average number of instructions to be executed by U, when simulating the execution of one instruction of a program P with input x. To obtain a complexity that does not depend on P or x, we introduce the concept of an introspection coefficient expressing the average number of instructions executed by U, for simulating the execution of one of its own instructions. We show how to obtain this coefficient by computing a square matrix whose elements are numbers of executed instructions when running selected parts of U on selected data. The coefficient then becomes the greatest eigenvalue of the matrix. We illustrate the approach using two examples of particularly efficient universal programs: one for a three-symbol Turing Machine (blank symbol not included) with an introspection coefficient of 3672.98, the other for an indirect addressing arithmetic machine with an introspection coefficient of 26.27.

The development of universal reasoning engines has been a main objective of AI since its very early days. The vision here is to relief system developers from having to worry about reasoning algorithms, focusing only on capturing the necessary knowledge, while delegating algorithmic considerations to these engines. Few decades after this original vision was first conceived, the field of AI is starting to bear its fruits, initially through SAT solvers, and more recently through knowledge compilers (and related model counters).

In this talk, I will discuss some of the progress in realizing this vision, highlighting both successes and missed opportunities. For example, on the satisfiability front, I will present a semantics for modern SAT solvers, which is somewhat distant from how these solvers are commonly understood. I will argue that the lack of this and similar semantics could be the reason behind the lack of recent leaps in SAT solving, which have been saught after since the zchaff solver was introduced many years ago. On the knowledge compilation front, I will review some of the key advancements, especially in relation to SAT solving and model counting, and point to some of the major gaps between what the theory says is possible and what current practice allows. I will argue that bridging this gap requires some novelties, especially in how systematic search is currently practiced. I will also discuss some recent breakthroughs that seem to have brought us closer to bridging this gap.

Relaxation is a theme that occurs in many problem solving methods. It is often associated with optimization, but relaxation plays an equally important role in finite-domain constraint programming and other discrete methods. This talk surveys a wide variety of relaxation methods, including linear relaxation and cutting planes, Lagrangean relaxation, the domain store and related relaxations, state space relaxation, relaxations in decomposition methods, as well as nonserial dynamic programming, mini buckets, and other relaxations based on simplifying the primal graph. Recognizing the role of relaxation can suggest improvements based on strengthening the relaxation. Consistency maintenance, for example, in effect strengthens relaxations. Other approaches include the use of such knowledge compilation devices as and/or trees and multivalued decision diagrams, and the solution of a relaxation dual problem.