Takeuti, Gaisi Computational complexity and proof theory. (English. Japanese original) Zbl 0681.03039 Sugaku Expo. 1, No. 1, 1-14 (1988); translation from Sûgaku 39, No. 2, 110-123 (1987). MSC: 03F05 03F25 68Q25 03D15 PDFBibTeX XMLCite \textit{G. Takeuti}, Sugaku Expo. 1, No. 1, 1--14 (1987; Zbl 0681.03039); translation from Sûgaku 39, No. 2, 110--123 (1987)
Hartmanis, J. Structural complexity column - Sparse complete sets of NP and the optimal collapse of the polynomial hierarchy. (English) Zbl 0661.68046 Bull. EATCS 32, 73-81 (1987). Reviewer: U.Schöning MSC: 68Q25 68Q05 03D15 PDFBibTeX XMLCite \textit{J. Hartmanis}, Bull. EATCS 32, 73--81 (1987; Zbl 0661.68046)
Babai, László Random oracles separate PSPACE from the polynomial-time hierarchy. (English) Zbl 0654.68052 Inf. Process. Lett. 26, 51-53 (1987). MSC: 68Q25 94C10 03D15 PDFBibTeX XMLCite \textit{L. Babai}, Inf. Process. Lett. 26, 51--53 (1987; Zbl 0654.68052) Full Text: DOI
Boppana, Ravi B.; Håstad, Johan; Zachos, Stathis Does co-NP have short interactive proofs ? (English) Zbl 0653.68037 Inf. Process. Lett. 25, 127-132 (1987). MSC: 68Q25 03D15 PDFBibTeX XMLCite \textit{R. B. Boppana} et al., Inf. Process. Lett. 25, 127--132 (1987; Zbl 0653.68037) Full Text: DOI
Wagner, Klaus W. More complicated questions about maxima and minima, and some closures of NP. (English) Zbl 0653.03027 Theor. Comput. Sci. 51, 53-80 (1987). MSC: 03D15 68Q25 PDFBibTeX XMLCite \textit{K. W. Wagner}, Theor. Comput. Sci. 51, 53--80 (1987; Zbl 0653.03027) Full Text: DOI
Takeuti, Gaisi Computational complexity and proof theory. (Japanese) Zbl 0646.03052 Sûgaku 39, No. 2, 110-123 (1987). Reviewer: M.Yasuhara MSC: 03F05 03F25 68Q25 03D15 PDFBibTeX XMLCite \textit{G. Takeuti}, Sūgaku 39, No. 2, 110--123 (1987; Zbl 0646.03052)