Nonuniform complexity classes specified by lower and upper bounds

DOI10.1051/ITA/1989230201771MaRDI QIDQ4730777zbMATH OpenOpenAlexFDO

Authors José L. Balcázar, Joaquim Gabarró

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

zbMATH Keywords

classes defined by exponential lower boundsclasses defined by polynomial and polylog upper boundsnonuniform complexity measuresoracle Turing machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Uniform characterizations of non-uniform complexity measures
• scientific article; zbMATH DE number 3917710
• Nonuniform lower bounds for exponential time classes
• Circuit Definitions of Nondeterministic Complexity Classes
• scientific article; zbMATH DE number 4090800

Cites work

• Asymptotical behaviour of some non-uniform measures
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Concise description of finite languages
• scientific article; zbMATH DE number 3808975 (Why is no real title available?)
• scientific article; zbMATH DE number 3829284 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3560742 (Why is no real title available?)
• scientific article; zbMATH DE number 3607492 (Why is no real title available?)
• scientific article; zbMATH DE number 3637282 (Why is no real title available?)
• scientific article; zbMATH DE number 1988954 (Why is no real title available?)
• scientific article; zbMATH DE number 3313249 (Why is no real title available?)
• On Relating Time and Space to Size and Depth
• On the complexity of branching programs and decision trees for clique functions
• On Time Versus Space
• Space-bounded hierarchies and probabilistic computations
• The network complexity and the Turing machine complexity of finite functions
• Uniform characterizations of non-uniform complexity measures

Cited in

(7)

• scientific article; zbMATH DE number 3917710 (Why is no real title available?)
• Uniform characterizations of non-uniform complexity measures
• Nonuniform complexity classes, decision graphs and homological properties of posets
• scientific article; zbMATH DE number 4041256 (Why is no real title available?)
• scientific article; zbMATH DE number 4090801 (Why is no real title available?)
• On tight separation for Blum measures applied to Turing machine buffer complexity
• Instruction sequence based non-uniform complexity classes

This page was built for publication: Nonuniform complexity classes specified by lower and upper bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4730777)