Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR98-045 | 17th July 1998 00:00

A Separation of Syntactic and Nonsyntactic (1,+k)-Branching Programs

RSS-Feed




TR98-045
Authors: Detlef Sieling
Publication: 5th August 1998 17:15
Downloads: 3666
Keywords: 


Abstract:

For (1,+k)-branching programs and read-k-times branching
programs syntactic and nonsyntactic variants can be distinguished. The
nonsyntactic variants correspond in a natural way to sequential
computations with restrictions on reading the input while lower bound
proofs are easier or only known for the syntactic variants. In this
paper it is shown that nonsyntactic (1,+k)-branching programs are
really more powerful than syntactic (1,+k)-branching programs by
presenting an explicitly defined function with polynomial size
nonsyntactic (1,+1)-branching programs but only exponential size
syntactic (1,+k)-branching programs. Another separation of these
variants of branching programs is obtained by comparing the complexity
of the satisfiability test for both variants.



ISSN 1433-8092 | Imprint