Expressibility and Nonuniform Complexity Classes

DOI10.1137/0219026MaRDI QIDQ3476275zbMATH OpenOpenAlexFDO

Authors Burkhard Molzan

Publication date 1990

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0219026

zbMATH Keywords

\(AC^ 0\)-circuits\(NC^ 1\)-circuitsbranching programscomputational complexitylogical expressibilitynonuniform complexity classes

Mathematics Subject Classification ID

Logic with extra quantifiers and operators (03C80) Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 4041256
• Expressibility and Parallel Complexity
• On uniformity within \(NC^ 1\)
• The power of nondeterminism in polynomial-size bounded-width branching programs
• scientific article; zbMATH DE number 4047115

Cited in

(9)

• Arithmetizing uniform NC
• A topological approach to non-uniform complexity
• Characterizing Polynomial and Exponential Complexity Classes in Elementary Lambda-Calculus
• Dichotomy theorems for families of non-cofinal essential complexity
• Extensions of an idea of McNaughton
• 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 1342210 (Why is no real title available?)

This page was built for publication: Expressibility and Nonuniform Complexity Classes

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