Abstract
A “promise problem” is a formulation of a partial decision problem. Complexity issues about promise problems arise from Even and Yacobi's work in public-key cryptography
This paper was written while the author visited the Computer Science Department, Technion, Haifa, Israel, with funds provided by the United States-Israel Educational Foundation (Fulbright Award). This research was supported in part by the National Science Foundation under grant MCS77-23493 A02.
Part of this research was done while the author visited the Electrical Engineering and Computer Sciences Dept., University of California at San Diego, La Jolla, CA, U.S.A.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Even, S. and Yacobi, Y., Cryptocomplexity and NP-completeness, Proc. of ICALP-80, Springer-Verlag Lecture Notes in Computer Science, Vol. 80, 195–207.
Ladner, R.E., On the structure of polynomial time reducibility, J. ACM 22 (1975).
Sipser, M., On relativization and the existence of complete sets, this conference.
Ullian, J.S., Partial algorithm problems for context free languages, Information and Control, Vol. 11, 1967, 80–101.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1982 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Selman, A.L., Yacobi, Y. (1982). The complexity of promise problems. In: Nielsen, M., Schmidt, E.M. (eds) Automata, Languages and Programming. ICALP 1982. Lecture Notes in Computer Science, vol 140. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0012795
Download citation
DOI: https://doi.org/10.1007/BFb0012795
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-11576-2
Online ISBN: 978-3-540-39308-5
eBook Packages: Springer Book Archive
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.