{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q1183604","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q1183604","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q1183604","kernelVersion":"v1","immutable":true,"modified":"2025-12-31T13:13:33Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q1183604","name":"Oracle branching programs and Logspace versus \\(P^*\\)","headline":"Oracle branching programs and Logspace versus \\(P^*\\)","description":"scientific article; zbMATH DE number 33434","url":"https://portal.mardi4nfdi.de/entity/Q1183604","datePublished":"1992-06-28","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q386052"},{"@id":"https://portal.mardi4nfdi.de/entity/Q208763"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q259032"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1016/0890-5401(91)90017-V","url":"https://doi.org/10.1016/0890-5401(91)90017-V"},"sameAs":["https://doi.org/10.1016/0890-5401(91)90017-V"],"comment":"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.","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q1117696"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3820014"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4142697"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3936210"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1217591"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1158753"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3694688"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3787477"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4128417"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4091421"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3821586"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1221749"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1235982"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4109298"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1106664"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4732127"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2537313"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3815544"}]},"provenance":{"prov:generatedAtTime":"2025-12-31T13:13:33Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}