如果P！= NP，P是否比非P问题多，反之亦然？

-2

如果P！= NP，那么比SuperPolynomial问题还有更多的多项式问题，反之亦然？如果P！= NP，P是否比非P问题多，反之亦然？

2014-12-13 Albert Hendriks

这个问题似乎是题外话题，因为它是关于计算理论，而不是关于具体的编程问题。尝试http://cs.stackexchange.com/，也许。 – amalloy 2014-12-13 12:03:46

@Gumbo他们不会欣赏CSTheory上的这个问题，这个问题适用于该领域的研究人员，而不是更偶然的提问者 - 计算机科学就是这样的地方。 – amalloy 2014-12-13 12:05:31

这个问题似乎是无关紧要的，因为它是关于CS理论的，但不是研究级别的CS理论，因此应该迁移到cs.stackexchange.com。 – templatetypedef 2014-12-16 02:15:52

从形式语言的角度来看，只有在P不和不可数许多问题P可数个问题。 P中的每个问题都可以通过一个确定性的多项式时间图灵机来解决，并且由于TM的数量可以是无限的，所以语言的数量可以是无限的。另一方面，总语言的数量等于可能的字符串子集的数量，因此在P中有不计其数的语言。有趣的是，这个结果独立于是否P = NP。

如果您将“问题”限制为“可决定的问题”（即可通过无限时间和存储空间的计算机解决的问题），那么我们知道只有数量可疑的总可确定问题。可数无限很多都是在P和，无论P = NP的，也有可数无穷多的人不P。

希望这有助于！

来源

2014-12-16 02:08:36 templatetypedef

给出我的问题，你的回答似乎是正确的，但我的意思是其他。对于那个很抱歉。我的意思是P问题与NP中的超级多项式问题。 – 2014-12-16 09:06:37

@AlbertHendriks哦，它又是一样的数字。你可以构造数量可以无限多的NP完全问题，如果P！= NP，那么这些问题都不会在P中。 – templatetypedef 2014-12-16 17:36:48

如果P！= NP，P是否比非P问题多，反之亦然？

回答

相关问题