试图确定一种语言的成员资格的非确定性机器会给出一个提示(称为“见证”或“证书”),以证明成员资格(没有为语言以外的元素提供此类见证;定义是不对称的)。
那么,如果一个非确定性算法能够在O(f(n))时间内解决一个问题,这是否意味着证书的长度是f(n)?输入的大小是n?
另外,如果一个算法A能够在O(f(n))时间内验证一个证书,这意味着一个非确定性算法的存在,它可以在O(f(n))时间内解决这个问题?
发布于 2012-08-27 20:51:01
IMHO:
no
,yes,
这里没有含意。如果一个非确定性算法能够解决O(f(n))中的一个问题,并且可以在O(g(n))中验证该解(证书或白度),则f和g是多个项,而不是NP难。(不一定NP-完全)
https://stackoverflow.com/questions/12148129
复制相似问题