GAP（图形可访问性问题）NP-Complete 吗？它有多项式和非确定性多项式算法来解决它，但我不认为这是一个标准，它通过显示它是 NP 和 NP-Hard => NP-Complete 来覆盖显示它是 NP-Complete 的基本方式。我从比我大的学生那里听到了这两个版本。那么到底是不是NP-Complete？
问问题
884 次
1 回答
2
维基百科说问题是NL-Complete，这意味着它也在P. 这使得它非常不可能NP-Complete。如果是这样，那将证明P=NP，这是一个非常古老且未解决的问题。人们普遍认为P≠NP.
您将无法证明它也不NP-Complete是，因为那将证明P≠NP.
如果你能证明它是NP-Complete或不是NP-Complete，你将获得一百万美元的奖励。
所以总而言之，答案是：这似乎不太可能，但你也不太可能在那个方向证明任何事情:)。
于 2013-09-10T21:02:04.667 回答