The power of nondeterminism in polynomial-size bounded-width branching programs
type: Item
instance of: scholarly article
title: The power of nondeterminism in polynomial-size bounded-width branching programs
zbMATH Open document ID: 0665.68041
DOI: 10.1016/0304-3975(88)90073-4
author: Christoph Meinel
published in: Theoretical Computer Science
publication date: 1988-01-01T00:00:00Z
review text: The nondeterministic branching programs introduced by the author [Lect. Notes Comput. Sci. 233, 527-535 (1986; Zbl 0611.03021)] are considered as computing devices. Since some types of branching programs (BPs) characterize the nonuniform counterparts of the fundamental complexity classes DLOG, NLOG P, NP and \(NC^ 1\) [\textit{D. A. Barinton}, ``Bounded- width polynomial-size branching programs recognizing exactly those languages in \(NC^ 1\)''. In: Proc. 18th Symp. Theory Comput. IEEE 1986, 1-5; cf. J. Comput. Syst. Sci. 38, No.1, 150-164 (1989); the author, Modified branching programs and their computational power. Habilitationsschrift, Berlin 1988] the power of nondeterminism for some special types of BPs is investigated. The following two results are established: (1) 1-time-only nondeterministic, polynomial size, bounded-width BPs characterize the class \(NC^ 1\), which means that their power is exactly the same as the power of polynomial-size, bounded-width BPs. (2) 2-times-only nondeterministic, polynomial-size, bounded-width BPs are as powerful as nondeterministic, polynomial size BPs, i.e., they characterize the class NP/poly.
reviewed by: Juraj Hromkovič
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 94C10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 4088935
zbMATH Keywords: nonuniform complexity classes
zbMATH Keywords: branching programs
zbMATH Keywords: nondeterminism
MaRDI profile type: Publication
full work available at URL: 0304-3975(88)90073-4
OpenAlex ID: W1964528982
cites work: Q3751569
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: Reducibility by algebraic projections
cites work: Q3762226
Recommended article: Q3783568
Recommended article: Q3779737
Recommended article: Modified branching programs and their computational power
Recommended article: Q4536358
Recommended article: Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
Recommended article: Comparing the sizes of nondeterministic branching read-k-times programs
Recommended article: A hierarchy result for read-once branching programs with restricted parity nondeterminism
Recommended article: Q4536401
Recommended article: On the hierarchy of nondeterministic branching k-programs
Recommended article: Q4739599
description: scientific article; zbMATH DE number 4088935