Computation in direct powers

During the last decade algebraic methods have played a major role in the investigation of socalled Constraint Satisfaction Problems (CSP) which arose in Computer Science and Artificial Intelligence. This class of problems encompasses a whole variety of classical decision problems, for example, satisfiability of Boolean formulas, graph colorability, or solvability of systems of linear equations. According to a conjecture of T. Feder and M. Vardi from 1993, CSPs should split exactly into 2 disjoint classes: those that can be solved in polynomial time (like linear equations) and those that are NP-complete (like checking whether a graph can be colored with 3 colors). NP- complete problems are the hardest problems for which a given solution can be verified in polynomial time. However we do not know how to find a solution for NP-complete problems efficiently. For every CSP an algebraic structure can be constructed such that solving the problem reduces to determining the intersection of subalgebras of direct powers of this algebra (Here an algebra is just a set with some operations that describe the computations that can be conducted with its elements). This crucial observation by A. Bulatov, P. Jeavons, and A. Krokin from 2000 makes this area of Computer Science amenable to algebraic methods. The need to understand and solve CSPs leads to new questions on how to represent subalgebras of direct powers and how to compute with them, e.g., to find generators, check membership, or determine intersections. The goal of this project is to develop such efficient computational methods for direct powers and their substructures. Hence it combines classical General Algebra and Computer Science. We aim to provide tools like those for solving linear equations in linear algebra for a much larger class of algebras that contains groups and lattices. In particular, we want to accomplish the following tasks for subalgebras of direct powers: 1. Find small, well-behaved generating sets. 2. Given a subalgebra by generators, check whether some element is contained in the subalgebra. 3. Given two subalgebras by their respective sets of generators, determine generators for their intersection. Algorithms for these problems serve as the most basic subroutines for solving equations and other computational problems over general algebraic structures. They would also provide new and transparent solutions for CSPs and related questions. Implementations of the developed methods will be made publicly available within established computer algebra systems, like GAP.

Relations are everywhere in the world. Mathematically they can be represented as pairs (e.g., a is less than b) or more generally tuples (e.g., each of the websites a, b, c refers to the other two). Many planning and scheduling problems can be formulated in the language of relations as Constraint Satisfaction Problems (CSP) in Computer Science and Artificial Intelligence. For example, finding a timetable means manipulating relations. To do that efficiently, this project aims to understand the structure of relations using Algebra.To every relation we can associate specific operations which allow us to compute with its tuples. In this sense relations become algebraic structures (more precisely subalgebras of direct powers of an algebra). This viewpoint makes it easier to recognize patterns, compare various relations, find tuples with certain properties, and possibly represent a very large relation just by a few of its elements (a generating set).With mathematicians and computer scientists in Canada, Spain, the UK, and the USA our team at JKU Linz covered three main areas in this project:1. How to find short presentations for relations? With N. Ru?kuc (St. Andrews) we investigated how to efficiently describe infinite subalgebras of powers, either finding new finite generating sets or showing that such finite descriptions are not possible.2. How to work with generators of relations? Given a short presentation of a relation by a few generators, our main goal is to compute with it efficiently. Un- fortunately when cutting down on the size of the presentation, basic tasks like checking membership, computing intersections, etc., often become quite time consuming in direct powers. The complexity usually grows exponentially in thelength of the tuples one considers. With A. Bulatov (Vancouver) and À . Szendrei (Boulder) we proved for the particular class of algebras with few subpowers that the basic tasks mentioned above can be solved in non-deterministic polynomial time (NP). Under additional conditions we found more efficient algorithms that even run in deterministic polynomial time (P).3. How to apply this in Computer Science? With H. Chen (San Sebastian) we used this theoretical background to study a generalization of CSP, namely Quantified Constraint Satisfaction Problems (QCSP), that appear for example in the verification of computer hardware. For certain classes of QCSP we could provide new algorithms and quantify their complexity: these problems are either in P (easy), NP-complete (hard), or PSPACE-complete (very hard).