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

文章基本信息

  • 标题:Nondeterminisic Sublinear Time Has Measure 0 in P
  • 本地全文:下载
  • 作者:John Hitchcock ; Adewale Sekoni
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2018
  • 卷号:2018
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    The measure hypothesis is a quantitative strengthening of the P = NP conjecture which asserts that NP is a nonnegligible subset of EXP. Cai, Sivakumar, and Strauss (1997) showed that the analogue of this hypothesis in P is false. In particular, they showed that NTIME[ n 1 11 ] has measure 0 in P. We improve on their result to show that the class of all languages decidable in nondeterministic sublinear time has measure 0 in P. Our result is based on DNF width and holds for all four major notions of measure on P.

  • 关键词:DNF formulas ; nondeterministic time classes ; Resource-bounded measure
国家哲学社会科学文献中心版权所有