Arithmetizing Uniform NC
- 8 July 1991
- journal article
- Published by Elsevier in Annals of Pure and Applied Logic
- Vol. 53 (1) , 1-50
- https://doi.org/10.1016/0168-0072(91)90057-s
Abstract
No abstract availableKeywords
This publication has 13 references indexed in Scilit:
- Regular languages in NC1Journal of Computer and System Sciences, 1992
- Expressibility and Nonuniform Complexity ClassesSIAM Journal on Computing, 1990
- Languages that Capture Complexity ClassesSIAM Journal on Computing, 1987
- Relational queries computable in polynomial timeInformation and Control, 1986
- A taxonomy of problems with fast parallel algorithmsInformation and Control, 1985
- An arithmetical characterization of NPTheoretical Computer Science, 1982
- Complexity classes and theories of finite modelsTheory of Computing Systems, 1981
- Complete problems for deterministic polynomial timeTheoretical Computer Science, 1976
- Existence and feasibility in arithmeticThe Journal of Symbolic Logic, 1971
- Untersuchungen ber das logische Schlie en. IMathematische Zeitschrift, 1935