Oracle branching programs and Logspace versus \(P^*\)
type: Item
instance of: scholarly article
title: Oracle branching programs and Logspace versus \(P^*\)
zbMATH Open document ID: 0744.68107
DOI: 10.1016/0890-5401(91)90017-V
author: David A. Mix Barrington
author: Pierre McKenzie
published in: Information and Computation
publication date: 1992-06-28T00:00:00Z
review text: The authors investigate the space complexity of the \(P\)- complete \(GEN\) problem by means of so-called oracle branching programs. \(GEN\) consists of determining membership in a subalgebra of a general (not necessarily associative) binary algebra (input as a multiplication table). natural subclasses of \(P\) can be expressed as natural subproblems for \(GEN\). Finally, the authors prove optimal lower bounds on the size of oracle branching programs for \(GEN\) with certain natural oracles.
Mathematics Subject Classification ID: 68R05
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 33434
zbMATH Keywords: \(P\)-complete \(GEN\) problem
zbMATH Keywords: branching programs
zbMATH Keywords: oracles
MaRDI profile type: MaRDI publication profile
cites work: Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
cites work: Finite monoids and the fine structure of NC 1
cites work: On Relating Time and Space to Size and Depth
cites work: A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
cites work: An observation on time-storage trade off
cites work: Towards a complexity theory of synchronous parallel computation
cites work: A taxonomy of problems with fast parallel algorithms
cites work: Problems complete for deterministic logarithmic space
cites work: Q4128417
cites work: Q4091421
cites work: Nondeterministic Space is Closed under Complementation
cites work: Space-bounded reducibility among combinatorial problems
cites work: Complete problems for deterministic polynomial time
cites work: New problems complete for nondeterministic log space
cites work: The complexity of parallel search
cites work: Q4732127
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: Q3815544
Recommended article: Q3975161
Recommended article: Q3974873
Recommended article: Polynomial size \(\Omega\)-branching programs and their computational power
Recommended article: Incremental branching programs
Recommended article: Q3787493
description: scientific article; zbMATH DE number 33434