补充资料：多项式时间归约

多项式时间归约
polynomial time reduction

L’(扛，则L就是节中(在多项式时间图灵归约下)“最困难”的，称其为够T-完全的。多项式时间图灵归约又称为库克归约。由多项式时间图灵归约的定义，很自然地可产生另一种重要的多项式时间归约，即多项式时间非确定图灵归约。多项式时间图灵归约与多项式时间非确定图灵归约的区别仅在于前者使用的是多项式时间确定型。拍cle机器，后者使用的是多项式时间非确定型优acle机器。 R.心印于1972年利用多项式时间多一归约来刻画NP类中的“最困难”问题类。同时，R.Karp给出了21个属于这类问题的实例，它们涉及到逻辑、图论及组合优化等学科中的经典计算问题。对于乏上的两个语言Ll，LZ，若存在多项式时间可计算函数f:乞份~乏甘，使得对任何xe艺诀，x任Ll当且仅当f(x)eL:，则称L;多项式时间多一归约到L:，记为Ll簇二LZ。这时，x任L，的判别可以通过计算f(x)，转化成f(x)‘LZ的判别。因此，L，(二LZ更直观地理解为Ll的计算不比LZ的计算困难。同群类似讨论，簇二也可定义在任何语言类留上，若存在Le留，使对于任何L‘任昭，都有L‘戳L，则称L为哈m-完全的。多项式时间多一归约又称为卡普归约。 递归论中的其它归约都可通过多项式变形成为一种多项式时间归约。上述介绍的几种归约关系已成为计算复杂性理论的重要工具。duox}angshi shlJ!Qn guiyue多项式时间归约(polynomial tilne阁uc·tion)一种常用的、归约函数是多项式时间可计算的复杂性归约。5.Gl)k于1971年利用多项式时间图灵归约，定义了NP类中的“最困难”问题。并证明了判别布尔表达式的可满足性问题(SA’T)，是这类问题的第一个问题。 假设所考虑的问题都已编码成字母表乏上的语言(实例的集合)。设L;，L:是乏上两个语言，若存在以L:为orade集的多项式时间图灵机M，其接受的语言为Ll，则称L，多项式时间图灵归约到LZ，记为Ll簇扛2。这时，对x是否属于L，的判别可转化为至多{x{的多项式个元素是否属于L:的判别，因此，LZ任P便导致Ll任P。从这种相对的意义上讲，Ll的计算不比I.z困难。 落孚可以是定义在任何语言类节上的一种二元前序关系，如果存在L任节，对于任何L’任留，都有

说明：补充资料仅用于学习参考，请勿用于其它任何用途。