One-way functions and the nonisomorphism of NP-complete sets (Q2639055): Difference between revisions

@@ Property / author @@
+Hemaspaandra, Lane A.
@@ Property / author: Hemaspaandra, Lane A. / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Isomorphisms and 1-L reductions
@@ Property / cites work: Isomorphisms and 1-L reductions / rank @@
+Normal rank
@@ Property / cites work @@
+Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
+Normal rank
@@ Property / cites work @@
+On Isomorphisms and Density of $NP$ and Other Complete Sets
+Normal rank
@@ Property / cites work @@
+Complete Problems and Strong Polynomial Reducibilities
+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 @@
+Complexity classes without machines: on complete languages for UP
+Normal rank
@@ Property / cites work @@
+Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
+Normal rank
@@ Property / cites work @@
+The isomorphism conjecture fails relative to a random oracle
+Normal rank
@@ Property / cites work @@
+Reductions among polynomial isomorphism types
@@ Property / cites work: Reductions among polynomial isomorphism types / rank @@
+Normal rank
@@ Property / cites work @@
+Relativized Questions Involving Probabilistic Algorithms
+Normal rank
@@ Property / cites work @@
+Relative complexity of checking and evaluating
@@ Property / cites work: Relative complexity of checking and evaluating / rank @@
+Normal rank
@@ Property / cites work @@
+On one-one polynomial time equivalence relations
@@ Property / cites work: On one-one polynomial time equivalence relations / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0304-3975(91)90323-t
+Normal rank
@@ Property / OpenAlex ID @@
+W1977930625
@@ Property / OpenAlex ID: W1977930625 / rank @@
+Normal rank