Every polynomial-time 1-degree collapses if and only if P = PSPACE

DOI10.2178/jsl/1096901763zbMath1081.03042OpenAlexW2085424088MaRDI QIDQ5311749

Stuart A. Kurtz, James S. Royer, Stephen A. Fenner

Publication date: 29 August 2005

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2178/jsl/1096901763

zbMATH Keywords

reducibilitydegreescomplexity classes

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (1)

Polynomial-time axioms of choice and polynomial-time cardinality

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On some natural complete operators
• On 1-truth-table-hard languages
• Labyrinth of thought. A history of set theory and its role in modern mathematics
• Complexity Measures for Public-Key Cryptosystems
• Time/Space Trade-Offs for Reversible Computation
• Creative sets

This page was built for publication: Every polynomial-time 1-degree collapses if and only if P = PSPACE