A hierarchy result for read-once branching programs with restricted parity nondeterminism

被引：1

作者：

Savicky, P ^{[1
]}

Sieling, D

机构：

[1] Acad Sci Czech Republ, Inst Comp Sci, Prague, Czech Republic

[2] Univ Dortmund, FB Informat, D-44221 Dortmund, Germany

来源：

THEORETICAL COMPUTER SCIENCE | 2005年 / 340卷 / 03期

关键词：

read-once branching programs; restricted parity nondeterminism; lower bounds on complexity; hierarchy;

D O I：

10.1016/j.tcs.2005.03.016

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Restricted branching programs are considered in complexity theory in order to study the space complexity of sequential computations and in applications as a data structure for Boolean functions. In this paper (circle plus, k)-branching programs and (v, k)-branching programs are considered, i.e., branching programs starting with a circle plus- (or V-)node with a fan-out of k whose successors are k read-once branching programs. This model is motivated by the investigation of the power of nondeterminism in branching programs and of similar variants that have been considered as a data structure. Lower bound methods and hierarchy results for polynomial size (circle plus, k)- and (V, k)-branching programs with respect to k are presented. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：594 / 605

页数：12

共 18 条

[1]

AJTAI M, 1999, P 40 FOCS, P60

[2] Time-space trade-off lower bounds for randomized computation of decision problems [J].

Beame, P ;

Saks, M ;

Sun, XD ;

Vee, E .

JOURNAL OF THE ACM, 2003, 50 (02) :154-195

[3] Time-space tradeoffs for branching programs [J].

Beame, P ;

Jayram, TS ;

Saks, M .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2001, 63 (04) :542-572

[4]

Beame Paul, 2002, P 34 ANN ACM S THEOR, P688

[5] Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams [J].

Bollig, B ;

Wegener, I .

THEORY OF COMPUTING SYSTEMS, 1999, 32 (04) :487-503

[6]

Borodin A., 1993, Computational Complexity, V3, P1, DOI 10.1007/BF01200404

[7]

BRYANT RE, 1986, IEEE T COMPUT, V35, P677, DOI 10.1109/TC.1986.1676819

[8]

BRYANT RE, 1992, COMPUT SURV, V24, P293, DOI 10.1145/136035.136043

[9]

JAIN J, 1992, BROWN MIT VLSI C, P210

[10] On P versus NP∧co-NP for decision trees and read-once branching programs [J].

Jukna, S ;

Razborov, A ;

Savicky, P ;

Wegener, I .

COMPUTATIONAL COMPLEXITY, 1999, 8 (04) :357-370

← 1 2 →