The relationships between the combinatorial and algebraic structure of problems, and their computational complexity are being studied. This investigation is using several approaches and concepts applicable to many types of problems in the mainstream of computer science and operations research. These include: expressing problems either in a finite algebraic or nonserial dynamic programming framework, efficient size-bounded reductions, local reductions, the concepts of polynomial and power index, several hypotheses on the complexity of SAT and relater problems, the computation dags associated with problem instances including their layouts in the plane, separator trees, the tight coupling of problems to resource-bounded computations, and various concepts of "nearness". The problem areas being considered include combinatorial problems, problems for finite or finitely presented algebraic structures, problems for recursively or hierarchically presented objects, and problems for several particularly important infinite algebraic structures.
