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

REDUCTIONS
POLYNOMIAL TIME
LOGSPACE
COMPLETE SETS

This publication has 4 references indexed in Scilit:

Relativization of questions about log space computability
Theory of Computing Systems, 1976
A quantifier characterization for nondeterministic log space
ACM SIGACT News, 1975
Reducibility among Combinatorial Problems
Published by Springer Nature ,1972
Relationships between nondeterministic and deterministic tape complexities
Journal of Computer and System Sciences, 1970