The major drawback to previous solution synthesis algorithms is that they do not attack computational complexity directly. They simply help arrange search in such a way that constraint satisfaction techniques can be optimally applied. This, however, limits their effectiveness to the bounds of constraint satisfaction itself.
Optimization problems can be exploited beyond the constraint satisfaction level. By partitioning a constraint graph into subgraphs which isolate, or ``cover'' one or more vertices, the values of those vertices can be optimized with respect to the other vertices in the subgraph. Solution synthesis techniques can then take advantage of this added pruning to significantly reduce the complexity of the problem.
Partitioning a graph is, in itself, a complex task. We greatly simplified this task by recognizing the factors that dominate the complexity of SS-HG and performing a secondary search for a partition which seeks to minimize those factors. This secondary search can be carried out heuristically because we can usually be satisfied with any reasonable partition. Optimal answers to the primary search are guaranteed even if the partition created led to a search that was not quite as efficient as it could have been. Future research in the area of graph partitioning may lead to further gains in efficiency.
We have demonstrated that these techniques can be used to process any tree-shaped input in linear time. Furthermore, we can reduce the dimensionality of any input problem by 1. We were able to process large two-dimensional problems that were intractable using previous methods. We applied the methodology to graph coloring problems, which are similar to many real-life problems such as scheduling. The techniques were also applied to processing natural language semantics. Complexities in the billions and trillions were reduced to the hundreds, with the result that knowledge-based semantic analysis can now be accomplished in linear time.
