Preview
Unable to display preview. Download preview PDF.
References
Hartmanis, J. and Hopcroft, J., Independence results in computer science, SIGACT News, vol. 8, no. 4 /1976/ pp. 13–24.
Hartmanis, J., Relations between diagonalization, proof systems, and complexity gaps, Theoretical Computer Science 8 /1979/ 239–253.
Landweber, L., Lipton, R., and Robertson, E., On the structure of sets in NP and other complexity classes, Theoretical Computer Science 15 /1981/ 181–200.
Schöning, U., A uniform approach to obtain diagonal sets in complexity classes, Theoretical Computer Science 18 /1982/ 95–103.
Sipser, M., On relativization and the existence of complete sets, 9th International Colloquium on Automata, Languages and Programing, Springer-Verlag, 1982.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1984 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kowalczyk, W. (1984). Some connections between presentability of complexity classes and the power of formal systems of reasoning. In: Chytil, M.P., Koubek, V. (eds) Mathematical Foundations of Computer Science 1984. MFCS 1984. Lecture Notes in Computer Science, vol 176. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0030318
Download citation
DOI: https://doi.org/10.1007/BFb0030318
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-13372-8
Online ISBN: 978-3-540-38929-3
eBook Packages: Springer Book Archive