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

1992/04/01 by Osamu Watanabe, Shouwen Tang · 1 citation
Computer Science · Mathematics · #Algorithm #Combinatorics #Completeness (order theory) #Computability, Logic, AI Algorithms #Computational complexity theory #Discrete mathematics #Logic, Reasoning, and Knowledge #Mathematical analysis #Mathematics #PSPACE #semigroups and automata theory

paper · doi:10.1016/0304-3975(92)90074-p

crossref issued 1992/04/01 · crossref published 1992/04/01 · crossref published-print 1992/04/01 · openalex publication_date 1992/04/01 · crossref created 2002/07/26 · crossref deposited 2019/04/12 · crossref indexed 2023/01/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23

Citations

• Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis
• The complexity of theorem-proving procedures
• NP is as easy as detecting unique solutions
• New directions in cryptography

Cited by

• PSPACE-complete [wikipedia]