Topics on the Complexity of Decision, Optimization, and Approximation Problems

本研究的目标是了解(a)问题的复杂性，(b)问题实例的代数、组合或图形结构，以及(c)用于描述问题实例的方法之间的相互关系。进一步的理解，本研究将在可能的情况下为所考虑的问题开发更有效的算法。研究将在以下几个不同的方面进行：对简洁描述的对象进行研究，以更好地理解如何使用描述的结构来有效地解决所描述的问题实例。非常有效的结构保留约简用于识别多项式时间或对数空间约简无法充分捕获的问题相似性。针对PSPACE-和EXPTIME-hard等困难问题，研究了有效的逼近算法和方案。最后，研究了几种硬自然决策、优化和近似优化问题的平均情况复杂度。

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.