首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:On Limited versus Polynomial Nondeterminism
  • 本地全文:下载
  • 作者:Uriel Feige ; Joe Kilian
  • 期刊名称:Chicago Journal of Theoretical Computer Science
  • 印刷版ISSN:1073-0486
  • 出版年度:1997
  • 卷号:1997
  • 出版社:MIT Press ; University of Chicago, Department of Computer Science
  • 摘要:

    In this paper, we show that efficient algorithms for some problems that require limited nondeterminism imply the subexponential simulation of nondeterministic computation by deterministic computation. In particular, if cliques of size O(log n) can be found in polynomial time, then nondeterministic time f(n) is contained in deterministic time 2^{O(\sqrt{f(n)polylog f(n)})}.

国家哲学社会科学文献中心版权所有