Methods for proving completeness via logical reductions
- 27 September 1993
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 118 (2), 193-229
- https://doi.org/10.1016/0304-3975(93)90109-7
Abstract
No abstract availableKeywords
This publication has 22 references indexed in Scilit:
- The complexity of iterated multiplicationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- On uniformity within NC1Journal of Computer and System Sciences, 1990
- Descriptive and computational complexityProceedings of Symposia in Applied Mathematics, 1989
- Nondeterministic Space is Closed under ComplementationSIAM Journal on Computing, 1988
- Languages that Capture Complexity ClassesSIAM Journal on Computing, 1987
- A taxonomy of problems with fast parallel algorithmsInformation and Control, 1985
- Constant Depth ReducibilitySIAM Journal on Computing, 1984
- Symmetric space-bounded computationTheoretical Computer Science, 1982
- On Two Problems in the Generation of Program Test PathsIEEE Transactions on Software Engineering, 1976
- Space-bounded reducibility among combinatorial problemsJournal of Computer and System Sciences, 1975