561
个编辑
更改
→Reduction约简
时间和空间层谱定理构成了大多数复杂类分离结果的基础。例如，时间层谱定理告诉我们P严格包含在EXPTIME中，而空间层谱定理告诉我们L严格包含在PSPACE中。
时间和空间层谱定理构成了大多数复杂类分离结果的基础。例如，时间层谱定理告诉我们P严格包含在EXPTIME中，而空间层谱定理告诉我们L严格包含在PSPACE中。
===Reduction约简===
===Reduction简化===
{{main|Reduction (complexity)}}
{{main|Reduction (complexity)}}
Many complexity classes are defined using the concept of a reduction. A reduction is a transformation of one problem into another problem. It captures the informal notion of a problem being at most as difficult as another problem. For instance, if a problem X can be solved using an algorithm for Y, X is no more difficult than Y, and we say that X reduces to Y. There are many different types of reductions, based on the method of reduction, such as Cook reductions, Karp reductions and Levin reductions, and the bound on the complexity of reductions, such as polynomial-time reductions or log-space reductions.
Many complexity classes are defined using the concept of a reduction. A reduction is a transformation of one problem into another problem. It captures the informal notion of a problem being at most as difficult as another problem. For instance, if a problem X can be solved using an algorithm for Y, X is no more difficult than Y, and we say that X reduces to Y. There are many different types of reductions, based on the method of reduction, such as Cook reductions, Karp reductions and Levin reductions, and the bound on the complexity of reductions, such as polynomial-time reductions or log-space reductions.
许多复杂性类是使用化简的概念来定义的。化简是将一个问题转化为另一个问题。它抓住了一个非正式的概念，即一个问题最多和另一个问题一样困难。例如，如果一个问题 x 可以用 y 的算法来解决，那么 x 并不比 y 困难，我们说 x 简化为 y。根据简化方法，简化有多种类型，如 Cook 简化、 Karp 简化和 Levin 简化，以及简化复杂度的界限，如多项式时间简化或对数空间简化。
The most commonly used reduction is a polynomial-time reduction. This means that the reduction process takes polynomial time. For example, the problem of squaring an integer can be reduced to the problem of multiplying two integers. This means an algorithm for multiplying two integers can be used to square an integer. Indeed, this can be done by giving the same input to both inputs of the multiplication algorithm. Thus we see that squaring is not more difficult than multiplication, since squaring can be reduced to multiplication.
The most commonly used reduction is a polynomial-time reduction. This means that the reduction process takes polynomial time. For example, the problem of squaring an integer can be reduced to the problem of multiplying two integers. This means an algorithm for multiplying two integers can be used to square an integer. Indeed, this can be done by giving the same input to both inputs of the multiplication algorithm. Thus we see that squaring is not more difficult than multiplication, since squaring can be reduced to multiplication.
最常用的简化是'''<font color="#ff8000"> 多项式时间图灵归约Polynomial-time reduction</font>'''。这意味着还原过程需要'''<font color="#ff8000"> 多项式时间</font>'''。例如，将一个整数平方的问题可以简化为两个整数相乘的问题。这意味着两个整数相乘的算法可以用来求一个整数的平方。实际上，这可以通过给乘法算法的两个输入提供相同的输入来实现。因此我们看到平方并不比乘法困难，因为平方可以简化为乘法。
This motivates the concept of a problem being hard for a complexity class. A problem X is hard for a class of problems C if every problem in C can be reduced to X. Thus no problem in C is harder than X, since an algorithm for X allows us to solve any problem in C. The notion of hard problems depends on the type of reduction being used. For complexity classes larger than P, polynomial-time reductions are commonly used. In particular, the set of problems that are hard for NP is the set of NP-hard problems.
This motivates the concept of a problem being hard for a complexity class. A problem X is hard for a class of problems C if every problem in C can be reduced to X. Thus no problem in C is harder than X, since an algorithm for X allows us to solve any problem in C. The notion of hard problems depends on the type of reduction being used. For complexity classes larger than P, polynomial-time reductions are commonly used. In particular, the set of problems that are hard for NP is the set of NP-hard problems.
这就产生了一个对于复杂类来说很难解决的问题的概念。如果C中的每一个问题都可以归结为X，那么对于一类问题C来说，问题X是困难的。因此，在C中没有问题比X更难，因为X的算法允许我们在C中解决任何问题。硬问题的概念取决于所用的约化类型。对于大于P的复杂度类，通常使用'''<font color="#ff8000"> 多项式时间图灵归约</font>'''。特别是对NP的难问题集就是'''<font color="#ff8000"> NP难问题</font>'''集。
If a problem X is in C and hard for C, then X is said to be complete for C. This means that X is the hardest problem in C. (Since many problems could be equally hard, one might say that X is one of the hardest problems in C.) Thus the class of NP-complete problems contains the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. Because the problem P = NP is not solved, being able to reduce a known NP-complete problem, Π<sub>2</sub>, to another problem, Π<sub>1</sub>, would indicate that there is no known polynomial-time solution for Π<sub>1</sub>. This is because a polynomial-time solution to Π<sub>1</sub> would yield a polynomial-time solution to Π<sub>2</sub>. Similarly, because all NP problems can be reduced to the set, finding an NP-complete problem that can be solved in polynomial time would mean that P = NP.]]
If a problem X is in C and hard for C, then X is said to be complete for C. This means that X is the hardest problem in C. (Since many problems could be equally hard, one might say that X is one of the hardest problems in C.) Thus the class of NP-complete problems contains the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. Because the problem P = NP is not solved, being able to reduce a known NP-complete problem, Π<sub>2</sub>, to another problem, Π<sub>1</sub>, would indicate that there is no known polynomial-time solution for Π<sub>1</sub>. This is because a polynomial-time solution to Π<sub>1</sub> would yield a polynomial-time solution to Π<sub>2</sub>. Similarly, because all NP problems can be reduced to the set, finding an NP-complete problem that can be solved in polynomial time would mean that P = NP.]]
如果一个问题X在C中并且对于C来说是难问题，那么X对于C来说是完全的。这意味着X是C中最难的问题（因为许多问题可能同样困难，我们可以说X是C中最难的问题之一），因此'''<font color="#ff8000"> 非确定性多项式时间复杂性类完全问题（NP完全问题）</font>'''类包含了NP中最困难的问题，从某种意义上说，它们是可能不在P中的最困难的问题。因为问题P = NP未被解决，如果能够将已知的NP完全问题Π<sub>2</sub>简化为另一个问题Π<sub>1</sub>，则表明Π<sub>1</sub>没有已知的多项式时间解。这是因为Π<sub>1</sub>的多项式时间解会产生Π<sub>2</sub>的多项式时间解。同样，由于所有NP问题都可以归结为集合，找到一个可以在多项式时间内解决的NP完全问题意味着P = NP。]]
==Important open problems重要的开放性问题==
==Important open problems重要的开放性问题==