设L是一种语言。对于每个自然 n，L 中长度为 n 的单词数为 n。
字母表是{0,1}。
我们假设 L 是 NP。为什么L-补体也在NP中？
最佳答案
由于 L 在 NP 中，因此它是可判定的(递归的)，其补码 L' 也是可判定的。现在，L' 可能在 NP 中，也可能不在 NP 中。但我们知道，对于任何字符串长度 n，只有一个字符串属于 L，这意味着对于任何字符串长度，除了一个字符串之外的所有字符串都属于 L'。
现在，NP 的定义表明问题的所有"is"实例都可以使用非确定性 TM 在多项式时间内解决。因此，给定 的一个实例，我们非确定性地获取长度为 n 的所有单词(其中 n 是 w 的长度)，并查看它是否在 L 中。一旦我们得到该单词(这样的单词肯定存在于恰好有一个长度为 n 的单词属于 L)，我们看看这个单词是否与 x 相同。如果不同(且仅当不同时)，x 在 L' 中，我们在多项式时间内得到这个答案，使 L' 成为 NP 问题。
关于complexity-theory - NP 中的 L 补体，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26843146/