AN ALGEBRAIC MODEL FOR COMBINATORIAL PROBLEMS

A new algebraic model, called the generalized satisfiability problem ( GSP) model, is introduced for representing and solving combinatorial p roblems. The GSP model is an alternative to the common method in the l iterature of representing such problems as language-recognition proble ms. In the GSP model, a problem instance is represented by a set of va riables together with a set of terms, and the computational objective is to find a certain sum of products of terms over a commutative semir ing. The model is general enough to express all the standard problems about sets of clauses and generalized clauses, all nonserial optimizat ion problems, and all {0,1}-linear programming problems. The model can also describe many graph problems, often in a very direct structure-p reserving way. Two important properties of the model are the following : 1. In the GSP model, one can naturally discuss the structure of indi vidual problem instances. The structure of a GSP instance is displayed in a ''structure tree.'' The smaller the ''weighted depth'' or ''chan nelwidth'' of the structure tree for a GSP instance, the faster the in stance can be solved by any one of several generic algorithms. 2. The GSP model extends easily so as to apply to hierarchically specified pr oblems and enables solutions to instances of such problems to be found directly from the specification rather than from the (often exponenti ally) larger specified object.