Abstract
Generalizing work of Schöning and others concerning gap language constructs recognizable in polynomial time we examine structural properties of reducibilities defined for various “lower” or “parallel” complexity classes. Finally we show how the proof techniques for the above can be used to show the existence of easy complexity cores for sets which cannot be decided in logarithmic space.
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
K. Ambos-Spies, Polynomial time degrees of NP-sets; in: E. Börger, Trends in Theoretical Computer Science, Computer Science Press, Rockville 1988, 95–142.
J. L. Balcázar, J. Díaz, J. Gabarró, Structural Complexity I; Springer, Berlin, 1988.
R. Book, D.-Z. Du, D. Russo, On polynomial and generalized complexity cores; Proc. 3rd Structure (1988), 236–250.
A. K. Chandra, L. Stockmeyer, U. Vishkin, Constant depth reducibility; SIAM J. Comput. (13) (1984), 423–439.
P. Chew, M. Machtey, A note on structure and looking back applied to the relative complexity of computable functions; J. Comput. System Sci.22 (1981), 53–59.
S. A. Cook, A taxonomy of problems with fast parallel Algorithms; Inf. & Contr. 64 (1985), 2–22.
R. E. Ladner, On the structure of polynomial time reducibility, J. ACM16 (1975), 155–171.
L. H. Landweber, R. J. Lipton, E. L. Robertson, On the structure of sets in NP and other complexity classes; Theoret. Comput. Sci.1 (1975), 103–123.
N. Lynch, On reducibility to complex or sparse sets; J.ACM22 (1975), 341–345.
P. Orponen, U. Schöning, The density and complexity of polynomial cores for intractable sets; Inf. & Contr.70 (1986), 54–68.
H. Rogers Jr., Theory of Recursive Functions and Effective Computability; McGraw-Hill, New York, 1967.
R. I. Soare, Recursively Enumerable Sets and Degrees; Springer, Berlin, 1986.
U. Schöning, A uniform approach to obtain diagonal sets in complexity classes; Theoret. Comput. Sci.18 (1982), 95–103.
U. Schöning, Minimal pairs for P, Theoret. Comput. Sci.31 (1984), 41–48.
D. Schmidt, The recursion-theoretic structure of complexity classes; Theoret. Comput. Sci.38 (1985), 143–156.
M. Serna, The parallel approximability of P-complete problems; Tesis doctoral, Facultat d'Informàtica de Barcelona (1990).
J. Torán, Structural properties of the counting hierarchies; Tesis doctoral, Facultat d'Informàtica de Barcelona (1988).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Vollmer, H. (1991). The gap-language-technique revisited. In: Börger, E., Kleine Büning, H., Richter, M.M., Schönfeld, W. (eds) Computer Science Logic. CSL 1990. Lecture Notes in Computer Science, vol 533. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-54487-9_72
Download citation
DOI: https://doi.org/10.1007/3-540-54487-9_72
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-54487-6
Online ISBN: 978-3-540-38401-4
eBook Packages: Springer Book Archive