The objective of the proposed research is to understand the interrelationships among (a) the complexity of problems, (b) the algebraic, combinatorial, or graphical structure of problem instances, and (c) the methods used to describe problem instances. Further given this understanding, this research will develop when possible more efficient algorithms for the problems considered. Research will be carried out on several different fronts as follows: Work on succinctly-described objects is carried out to better understand how the structure of the description can be used to efficiently solve the problem instances described. Very efficient structure-preserving reductions are used to identify problem similarities not adequately captured by polynomial time or log space reductions. Work on efficient approximation algorithms and scheme is carried out for hard problems including PSPACE- and EXPTIME-hard problems. Finally, work is initiated on the average case complexity of several hard natural decision, optimization, and approximate optimization problems.
