复杂性类

在计算复杂性理论中，复杂性类是一组基于资源的相关复杂性的计算问题。两种最常分析的资源是时间和内存。一般来说，一个复杂度类是以一种计算问题的类型、一种计算模型和一种有约束的资源如时间或内存来定义的。特别是，大多数复杂性类由图灵机可解决的决策问题组成，并以其时间或空间（内存）要求来区分。例如，P类是可由确定性图灵机在多项式时间内解决的决策问题的集合。然而，还有许多复杂性类是以其他类型的问题（如计数问题和函数问题）和使用其他计算模型来定义的。对复杂性等级之间关系的研究是理论计算机科学的一个主要研究领域。复杂性类通常有一般的层次，例如，已知一些基本的时间和空间复杂性类以下列方式相互联系。NL⊆P⊆NP⊆PACE⊆EXPTIME⊆EXPSPACE（其中⊆表示子集关系）。然而，许多关系还不为人所知；例如，计算机科学中最有名的开放问题之一是关于P是否等于NP的问题。类之间的关系常常回答关于计算的基本性质的问题。例如，P与NP的问题直接关系到非确定性是否给计算机增加了任何计算能力，以及具有可以快速检查正确性的解决方案的问题是否也可以被快速解决。

复杂性类是相关计算问题的集合。它们被定义为在特定的计算资源如时间或内存方面，解决其中所包含的问题的计算难度。更正式地说，复杂性类的定义包括三件事：一种计算问题的类型，一种计算模型，以及一种受限的计算资源。特别是，大多数复杂度类是由图灵机在有限的时间或空间资源下可以解决的决策问题组成的。例如，复杂性类P被定义为可由确定性图灵机在多项式时间内解决的决策问题的集合。

直观地说，计算问题只是一个可以用算法解决的问题。例如，自然数是n{displaystylen}是素数吗？就是一个计算问题。一个计算问题在数学上被表示为问题的答案集合。

理论计算机科学中最常分析的问题是决策问题--那种可以被提出来作为是-否问题的问题。例如，上面的首要性例子就是一个决策问题的例子，因为它可以用是-否问题来表示，就是自然数素数。就计算理论而言，一个决策问题被表示为运行正确算法的计算机会回答是的输入字符串的集合。是代表自然数的字符串集合，当输入到一台运行正确测试素数的算法的计算机中时，该算法会回答是，这个数字是素数。这种"是"-"否"的格式通常被等效为接受-拒绝；也就是说，如果决策问题的答案是"是"，算法就接受输入的字符串，如果答案是"否"，算法就拒绝。虽然有些问题不容易被表达为决策问题，但它们还是包含了广泛的计算问题。