我对这个网站还不太熟悉，如果这个问题出现在错误的部分，我深表歉意。我正在上算法分析课，我的作业有一个问题，如果我能得到一些指导，我将不胜感激。
我要解决的问题是证明空语言和{0，1}*是p语言中唯一在多项式时间缩减方面不完全的语言（clrs第3版中的问题34.3-6）。问题的第一部分看起来相当简单（证明空的语言标准）。然而，当我必须证明{0，1}*的标准时，我甚至不知道从哪里开始。我不是在寻找答案，但是我希望能得到一些关于如何开始思考这个问题的指导。提前谢谢！
最佳答案
关于多项式时间归约的p完全性的定义是，问题l是p完全的，如果：
我在P
从p到l的每一个问题都有一个多项式时间归约。
对于L = {}，给定一个问题X，即X!= {}，您需要找到每个p（设为X）实例的缩减x，p(x)在L中，当且仅当x在X中时。
假设存在这样的p。但是，由于X != {}，有一些x，因此x在X中，并且p(x)不能在L中，因为L是空的。矛盾的存在这样的p。
用任何语言对L={0,1}*重复同样的操作，并且X != {0,1}*不在x中。
关于algorithm - NP完整性和可还原性，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29068496/