A complexity theory based on Boolean algebra
- 1 October 1981
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 244-253
- https://doi.org/10.1109/sfcs.1981.3
Abstract
No abstract availableKeywords
This publication has 13 references indexed in Scilit:
- Polynomial algorithms in linear programmingUSSR Computational Mathematics and Mathematical Physics, 1980
- On uniform circuit complexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Linear programming is log-space hard for PInformation Processing Letters, 1979
- Deterministic CFL's are accepted simultaneously in polynomial time and log squared spacePublished by Association for Computing Machinery (ACM) ,1979
- Fast Parallel Matrix Inversion AlgorithmsSIAM Journal on Computing, 1976
- Circuit size is nonlinear in depthTheoretical Computer Science, 1976
- Complete problems for deterministic polynomial timePublished by Association for Computing Machinery (ACM) ,1974
- Reducibility among Combinatorial ProblemsPublished by Springer Science and Business Media LLC ,1972
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970