On polynomial-time Turing and many-one completeness in PSPACE
From MaRDI portal
Publication:1193869
DOI10.1016/0304-3975(92)90074-PzbMath0773.68033MaRDI QIDQ1193869
Publication date: 27 September 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
03D30: Other degrees and reducibilities in computability and recursion theory
Related Items
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