On polynomial-time Turing and many-one completeness in PSPACE

DOI10.1016/0304-3975(92)90074-PzbMath0773.68033MaRDI QIDQ1193869

Osamu Watanabe, Shouwen Tang

Publication date: 27 September 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

reducibilitiesPSPACE-complete sets

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (1)

Cook versus Karp-Levin: Separating completeness notions if NP is not small

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A natural encoding scheme proved probabilistic polynomial complete
• On self-reducibility and weak P-selectivity
• NP is as easy as detecting unique solutions
• A comparison of polynomial time completeness notions
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Some consequences of the existnce of pseudorandom generators
• Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
• Complexity Measures for Public-Key Cryptosystems
• New directions in cryptography
• Completeness, Approximation and Density
• On Reducibility to Complex or Sparse Sets
• P-Printable Sets
• The complexity of theorem-proving procedures

This page was built for publication: On polynomial-time Turing and many-one completeness in PSPACE