论文标题
多组矩阵时间和空间的完整性
Completeness in Polylogarithmic Time and Space
论文作者
论文摘要
复杂性理论可以看作是对计算与应用之间关系的研究，将前者理解为复杂性类别，而后者则是问题。完整性结果显然是该观点的核心。当前应用导致的许多天然算法具有多组矩阵时间（Polylogtime）或空间复杂性（Polyrogspace）。但是，完全问题的经典KARP概念在这些复杂性类别中不能很好地发挥作用。众所周知，在对数空间中，多个减少的polygspace没有完全的问题。在本文中，我们显示了确定性和非确定性的聚类以及各个级别的各级层次层次结构的相似结果。我们通过遵循不同的策略来证明每个班级内部问题的适当层次结构的存在来实现这一目标。然后，我们从电路复杂性概念的概念中提出了一个替代性概念，并证明了在这个新概念下的PolylogSpace（均匀）完整问题的存在。由于这一结果，我们得到完整的问题仍然可以在研究聚类和其他经典复杂性类别之间的相互关系中发挥重要作用。
Complexity theory can be viewed as the study of the relationship between computation and applications, understood the former as complexity classes and the latter as problems. Completeness results are clearly central to that view. Many natural algorithms resulting from current applications have polylogarithmic time (PolylogTime) or space complexity (PolylogSpace). The classical Karp notion of complete problem however does not plays well with these complexity classes. It is well known that PolylogSpace does not have complete problems under logarithmic space many-one reductions. In this paper we show similar results for deterministic and non-deterministic PolylogTime as well as for every other level of the polylogarithmic time hierarchy. We achieve that by following a different strategy based on proving the existence of proper hierarchies of problems inside each class. We then develop an alternative notion of completeness inspired by the concept of uniformity from circuit complexity and prove the existence of a (uniformly) complete problem for PolylogSpace under this new notion. As a consequence of this result we get that complete problems can still play an important role in the study of the interrelationship between polylogarithmic and other classical complexity classes.
