首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >复杂类中证书的长度

问复杂类中证书的长度
EN

Stack Overflow用户
提问于 2012-08-27 19:13:53
回答 1查看 181关注 0票数 0

试图确定一种语言的成员资格的非确定性机器会给出一个提示(称为“见证”或“证书”),以证明成员资格(没有为语言以外的元素提供此类见证;定义是不对称的)。

那么,如果一个非确定性算法能够在O(f(n))时间内解决一个问题,这是否意味着证书的长度是f(n)?输入的大小是n?

另外,如果一个算法A能够在O(f(n))时间内验证一个证书,这意味着一个非确定性算法的存在,它可以在O(f(n))时间内解决这个问题?

EN

回答 1

Stack Overflow用户

发布于 2012-08-27 20:51:01

IMHO:

  • 那么,如果一个非确定性算法能够在O(f(n))时间内解决一个问题,这是否意味着证书的长度是f(n)?

no

  • 输入的大小是n?

,yes,

  • 另外,如果一个算法A能够在O(f(n))时间内验证一个证书,这意味着一个非确定性算法的存在,它可以在O(f(n))时间内解决这个问题?

这里没有含意。如果一个非确定性算法能够解决O(f(n))中的一个问题,并且可以在O(g(n))中验证该解(证书或白度),则f和g是多个项,而不是NP难。(不一定NP-完全)

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/12148129

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档