On polynomial-time Turing and many-one completeness in PSPACE (Q1193869): Difference between revisions

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