Nonuniform complexity classes specified by lower and upper bounds
From MaRDI portal
Publication:4730777
DOI10.1051/ita/1989230201771zbMath0681.68054OpenAlexW109090985MaRDI QIDQ4730777
Joaquim Gabarró, José L. Balcázar
Publication date: 1989
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/92330
oracle Turing machinesnonuniform complexity measuresclasses defined by exponential lower boundsclasses defined by polynomial and polylog upper bounds
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Cites Work
- Space-bounded hierarchies and probabilistic computations
- Concise description of finite languages
- The network complexity and the Turing machine complexity of finite functions
- Uniform characterizations of non-uniform complexity measures
- On the complexity of branching programs and decision trees for clique functions
- Asymptotical behaviour of some non-uniform measures
- On Time Versus Space
- On Relating Time and Space to Size and Depth
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Nonuniform complexity classes specified by lower and upper bounds
