文章基本信息

标题：Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs
本地全文：下载
作者：Stephen Cook ; Jeff Edmonds ; Venkatesh Medabalimi 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：55
页码：36:1-36:13
DOI：10.4230/LIPIcs.ICALP.2016.36
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We prove exponential lower bounds on the size of semantic read-once 3-ary nondeterministic branching programs. Prior to our result the best that was known was for D-ary branching programs with |D| >= 2^{13}.
关键词：Branching Programs; Semantic; Non-deterministic; Lower Bounds