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

文章基本信息

  • 标题:A Note on Read-k Times Branching Programs
  • 本地全文:下载
  • 作者:Stasys Jukna
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:1994
  • 卷号:1994
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    A syntactic read-k times branching program has the restriction that no variable occurs more than k times on any path (whether or not consistent). We exhibit an explicit Boolean function f which cannot be computed by nondeterministic syntactic read-k times branching programsof size less than exp(\sqrt{n}}k^{-2k}), although its complement 1-f has a nondeterministic syntactic read-oncebranching program of polynomial size.This, in particular, means that the nonuniform analogue ofNLOGSPACE = co-NLOGSPACE fails for syntactic read-k times networkswith k = o(\log n). We also show that (even for k=1) the syntactic model is exponentially weaker then more realistic "nonsyntactic" one.

  • 关键词:branching programs; lower bounds; read-k times networks
国家哲学社会科学文献中心版权所有