更改

===P和NP===

===P和NP===

从概念上讲，判定问题是指从字母集合Σ中选出一些字符串''w''作为输入数据，根据这些输入数据判断输出“是”还是“否”。如果存在一种算法（如图灵机或无内存使用限制的电脑程序）对输入任意长度为''n''的字符串，在最多''cn^k'' 个步骤内可以输出正确结果，其中''k''和''c''是与输入字符串无关的常数，那么我们称这个问题可以在多项式时间内求解，这类问题就叫做P类问题。形式上，P定义为所有能被确定多项式时间图灵机判定的语言集合。也就是：

从概念上讲，判定问题是指从字母集合Σ中选出一些字符串''w''作为输入数据，根据这些输入数据判断输出“是”还是“否”。如果存在一种算法（如图灵机或无内存使用限制的电脑程序）对输入任意长度为''n''的字符串，在最多''cn^k'' 个步骤内可以输出正确结果，其中''k''和''c''是与输入字符串无关的常数，那么我们称这个问题可以在多项式时间内求解，这类问题就称为P类问题。形式上，P定义为所有能被确定多项式时间图灵机判定的语言集合。也就是：

<math>\mathbf{P} = \{ L : L=L(M) \text{ for some deterministic polynomial-time Turing machine } M \}</math> 其中 <math>L(M) = \{ w\in\Sigma^{*}: M \text{ accepts } w \}</math>

<math>\mathbf{P} = \{ L : L=L(M) \text{ for some deterministic polynomial-time Turing machine } M \}</math> 其中 <math>L(M) = \{ w\in\Sigma^{*}: M \text{ accepts } w \}</math>