结构复杂度理论

在计算复杂度理论内，结构复杂度理论（英语：structural complexity theory)或者简单的结构复杂度（英语：structural complexity)是专门研究复杂度类本身，而非单一问题的可计算性或算法的学问。这理论牵涉到研究各种复杂度类的内部结构以及不同复杂度类之间的关系。[1]

这理论的出现，是在解决这类问题中第一个，也仍是最重要的一个问题：P/NP问题时，不断失败的一个结果。许多这方面的研究都基于 P != NP这个假设，以及一个更深远的推测：多项式时间谱系内的复杂度类个数是无限的。[1]

这个领域的一些主要研究方向有：[1]

  • 各种未解的问题，对复杂度类之间关系所产生的影响。
  • 各种限制资源的归约方式以及相对应的完全语言。
  • 各种对于读取跟储存资料的限制以及使用方法，会对复杂度类产生的影响。

相关条目

参考资料

  1. ^ 1.0 1.1 1.2 Juris Hartmanis, "New Developments in Structural Complexity Theory" (invited lecture), Proc. 15th International Colloquium on Automata, Languages and Programming, 1988 (ICALP 88), Lecture Notes in Computer Science, vol. 317 (1988), pp. 271-286.