Oracle branching programs and Logspace versus \(P^*\) (Q1183604)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Oracle branching programs and Logspace versus \(P^*\) |
scientific article; zbMATH DE number 33434
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Oracle branching programs and Logspace versus \(P^*\) |
scientific article; zbMATH DE number 33434 |
Statements
Oracle branching programs and Logspace versus \(P^*\) (English)
0 references
28 June 1992
0 references
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.
0 references
\(P\)-complete \(GEN\) problem
0 references
branching programs
0 references
oracles
0 references
0 references
