更改

A standard method for getting lower bounds of complexity consists of reducing a problem to another problem. More precisely, suppose that one may encode a problem  of size  into a subproblem of size  of a problem , and that the complexity of  is <math>\Omega(g(n)).</math> Without loss of generality, one may suppose that the function  increases with  and has an inverse function . Then the complexity of the problem  is <math>\Omega(g(h(n))).</math> This is this method that is used for proving that, if P ≠ NP (an unsolved conjecture), the complexity of every NP-complete problem is <math>\Omega(n^k),</math> for every positive integer .

A standard method for getting lower bounds of complexity consists of reducing a problem to another problem. More precisely, suppose that one may encode a problem  of size  into a subproblem of size  of a problem , and that the complexity of  is <math>\Omega(g(n)).</math> Without loss of generality, one may suppose that the function  increases with  and has an inverse function . Then the complexity of the problem  is <math>\Omega(g(h(n))).</math> This is this method that is used for proving that, if P ≠ NP (an unsolved conjecture), the complexity of every NP-complete problem is <math>\Omega(n^k),</math> for every positive integer .

获得复杂度下限的标准方法包括将一个问题转化为另一个问题。更准确地说，假设一个大小为{{mvar|n}}的问题{{mvar|A}}可以编码成大小为{{math|''f''(''n'')}}的问题{{mvar|B}}，则问题{{mvar|A}}的复杂度为<math>\Omega(g(n)).</math>。不失一般性地，我们可以假设函数{{mvar|f}}随着{{mvar|n}}的增加而增加，并且有一个'''<font color="#ff8000">反函数 inverse function</font>'''{{mvar|h}}，那么问题{{mvar|B}}的复杂度就是<math>\Omega(g(h(n))).</math>。这个方法可以用来证明，若 P ≠ NP (一个未解决的猜想) ，对于每个正整数{{mvar|k}}，每个'''<font color="#ff8000">NP完全问题 NP-complete problem</font>''' 的复杂度都是 <math>\Omega(n^k),</math>。

获得复杂度下限的标准方法包括将一个问题转化为另一个问题。更准确地说，假设一个大小为{{mvar|n}}的问题{{mvar|A}}可以编码成大小为{{math|''f''(''n'')}}的问题{{mvar|B}}，则问题{{mvar|A}}的复杂度为<math>\Omega(g(n)).</math>。不失一般性地，我们可以假设函数{{mvar|f}}随着{{mvar|n}}的增加而增加，并且有一个'''<font color="#ff8000">反函数 inverse function</font>'''{{mvar|h}}，那么问题{{mvar|B}}的复杂度就是<math>\Omega(g(h(n))).</math>。这个方法可以用来证明，若'''<font color="#ff8000">P ≠ NP</font>'''(一个未解决的猜想) ，对于每个正整数{{mvar|k}}，每个'''<font color="#ff8000">NP完全问题 NP-complete problem</font>''' 的复杂度都是 <math>\Omega(n^k),</math>。

==Use in algorithm design==

==Use in algorithm design==