Expressibility and Nonuniform Complexity Classes

DOI10.1137/0219026zbMath0698.68047OpenAlexW2035308802MaRDI QIDQ3476275

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

computational complexitybranching programslogical expressibilitynonuniform complexity classes\(AC^ 0\)-circuits\(NC^ 1\)-circuits

Mathematics Subject Classification ID

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

Related Items

Extensions of an idea of McNaughton, Arithmetizing uniform \(NC\)