JCSS, Volume 39

Volume 39, Number 1, August 1989

Selected Papers of the Structure in Complexity Theory Conference, June 16-19, 1987 - Part 1

Moon-Jung Chung, Bala Ravikumar: Strong Nondeterministic Turing Reduction - A Technique for Proving Intractability. 2-20 BibTeX
Martín Abadi, Joan Feigenbaum, Joe Kilian: On Hiding Information from an Oracle. 21-50 BibTeX
Daniel Leivant: Descriptive Characterizations of Computational Complexity. 51-83 BibTeX
Uwe Schöning: Probabilistic Complexity Classes and Lowness. 84-100 BibTeX
Eric Allender: Some Consequences of the Existence of Pseudorandom Generators. 101-124 BibTeX

Leonidas J. Guibas, John Hershberger: Optimal Shortest Path Queries in a Simple Polygon. 126-152 BibTeX
N. Dadoun, David G. Kirkpatrick: Parallel Construction of Subdivision Hierarchies. 153-165 BibTeX
Joseph C. Culberson, Robert A. Reckhow: Orthogonally Convex Coverings of Orthogonal Polygons without Holes. 166-204 BibTeX
Paul Chew: There are Planar Graphs Almost as Good as the Complete Graph. 205-219 BibTeX
Subhash Suri: Computing Geodesic Furthest Neighbors in Simple Polygons. 220-235 BibTeX
Kokichi Sugihara: On Finite-Precision Representations of Geometric Objects. 236-247 BibTeX

Selected Papers of the Structure in Complexity Theory Conference, June 16-19, 1987 - Part 2

Klaus Ambos-Spies: Honest Polynomial Time Reducibilities and the P = ? NP Problem. 250-281 BibTeX
Jim Kadin: P^(NP[O(log n)]) and Sparse Turing-Complete Sets for NP. 282-298 BibTeX
Lane A. Hemachandra: The Strong Exponential Hierarchy Collapses. 299-322 BibTeX
Raymond Greenlaw: Ordered Vertex Removal and Subgraph Problems. 323-342 BibTeX
Pierre America, Jan J. M. M. Rutten: Solving Reflexive Domain Equations in a Category of Complete Metric Spaces. 343-375 BibTeX
A. G. Robinson, A. J. Goldman: The Set Coincidence Game: Complexity, Attainability, and Symmetric Strategies. 376-387 BibTeX