更改

#''L'' ∈ NP

#''L'' ∈ NP

#任何在NP中的''L''是可多项式时间归约为''L''（记作<math>L' \leq_{p} L</math>），其中<math>L' \leq_{p} L</math>，当且仅当满足以下两个条件：【无法理解这个逻辑】

#任何在NP中的''L''可多项式时间归约为''L''（记作<math>L' \leq_{p} L</math>），其中<math>L' \leq_{p} L</math>，当且仅当满足以下两个条件：【无法理解这个逻辑】

##存在一个 ''f'' : Σ* → Σ* 使得对于所有在Σ*中的''w''，有<math>(w\in L' \Leftrightarrow f(w)\in L)</math>；并且

##存在一个 ''f'' : Σ* → Σ* 使得对于所有在Σ*中的''w''，有<math>(w\in L' \Leftrightarrow f(w)\in L)</math>；并且

##存在一个多项式时间图灵机，它对于任何输入''w''以 ''f''(''w'') 停机。【不清楚如何翻译解释f(w)，在[[wikipedia:P_versus_NP_problem#NP-completeness_2|链接]]中原句为there exists a polynomial-time Turing machine that halts with ''f''(''w'') on its tape on any input ''w''.】

##存在一个多项式时间图灵机，它对于任何输入''w''以 ''f''(''w'') 停机。【不清楚如何翻译解释f(w)，在[[wikipedia:P_versus_NP_problem#NP-completeness_2|链接]]中原句为there exists a polynomial-time Turing machine that halts with ''f''(''w'') on its tape on any input ''w''.】

另一种方法，如果''L'' ∈ NP，有另一个NP完全问题能在多项式时间内归约为''L''，那么L是NP完全问题。这是证明一个新问题是NP完全问题的常用方法。

另一种方法是，如果''L'' ∈ NP，并且有另一个NP完全问题能在多项式时间内归约为''L''，那么L是NP完全问题。这是证明一个新问题是NP完全问题的常用方法。

==Popular culture==

==Popular culture==