Abstract
It is shown that there is a length-preserving relation that is NP-complete such that the transitive closure of the relation is PSPACE-complete.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R. Book. Polynomial space and transitive closure,SIAM J. Computing 8, 434–439 (1979)
S. Cook. The complexity of theorem-proving procedures,Proc. ACM Symp. Theory of Computing, 151–158 (1971).
J. Hartmanis and J. Simon. On the power of multiplication in random access machines,15th IEEE Symp. Switching and Automata Theory, 13–23 (1974).
N. Jones. Classes of automata and transitive closure,Info. Control 13, 207–229 (1968).
R. Karp. Reducibilities among combinatorial problems,Complexity of Computer Computations (R. Miller, J. Thatcher, eds.). New York: Plenum Press, 1972.
L. Stockmeyer. The polynomial-time hierarchy,Theoret. Comp. Sci. 3, 1–22 (1977).
C. Wrathall. Complete sets and the polynomial-time hierarchy,Theoret. Comp. Sci. 3, 23–33 (1977).
Author information
Authors and Affiliations
Additional information
This research was supported in part by the National Science Foundation under Grant MCS80-11979.
Rights and permissions
About this article
Cite this article
Book, R.V., Wrathall, C. A note on complete sets and transitive closure. Math. Systems Theory 15, 311–313 (1981). https://doi.org/10.1007/BF01786987
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01786987