On Structure Preserving Reductions
- 1 May 1978
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 7 (2), 119-126
- https://doi.org/10.1137/0207010
Abstract
The concept of reduction between problems is strengthened. Certain standard problems are shown to be complete in the new and stronger sense. Applications to the number of solutions of particular problems are presented.Keywords
This publication has 4 references indexed in Scilit:
- Relativization of questions about log space computabilityTheory of Computing Systems, 1976
- A quantifier characterization for nondeterministic log spaceACM SIGACT News, 1975
- Reducibility among Combinatorial ProblemsPublished by Springer Science and Business Media LLC ,1972
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970