On the reducibility of sets inside NP to sets with low information content (Q1765294): Difference between revisions

@@ Property / DOI @@
-.1016/j.jcss.2004.03.003
@@ Property / DOI: 10.1016/j.jcss.2004.03.003 / rank @@
-Normal rank
@@ Property / author @@
+Ogihara, Mitsunori
@@ Property / author: Ogihara, Mitsunori / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.jcss.2004.03.003
+Normal rank
@@ Property / OpenAlex ID @@
+W4240832909
@@ Property / OpenAlex ID: W4240832909 / rank @@
+Normal rank
@@ Property / cites work @@
+A note on decision versus search for graph automorphism
+Normal rank
@@ Property / cites work @@
+Quasi-linear truth-table reductions to \(p\)-selective sets
+Normal rank
@@ Property / cites work @@
+A very hard log-space counting class
@@ Property / cites work: A very hard log-space counting class / rank @@
+Normal rank
@@ Property / cites work @@
+Q4281491
@@ Property / cites work: Q4281491 / rank @@
+Normal rank
@@ Property / cites work @@
+A structural property of regular frequency computations.
+Normal rank
@@ Property / cites work @@
+Q2742600
@@ Property / cites work: Q2742600 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4259996
@@ Property / cites work: Q4259996 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximable sets
@@ Property / cites work: Approximable sets / rank @@
+Normal rank
@@ Property / cites work @@
+The (Non)enumerability of the determinant and the rank
+Normal rank
@@ Property / cites work @@
+\(p\)-selective self-reducible sets: a new characterization of P
+Normal rank
@@ Property / cites work @@
+Structure and importance of logspace-MOD class
@@ Property / cites work: Structure and importance of logspace-MOD class / rank @@
+Normal rank
@@ Property / cites work @@
+Enumerative counting is hard
@@ Property / cites work: Enumerative counting is hard / rank @@
+Normal rank
@@ Property / cites work @@
+Division in logspace-uniform<i>NC</i><sup>1</sup>
@@ Property / cites work: Division in logspace-uniform<i>NC</i><sup>1</sup> / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of promise problems with applications to public-key cryptography
+Normal rank
@@ Property / cites work @@
+Cryptocomplexity and NP-completeness
@@ Property / cites work: Cryptocomplexity and NP-completeness / rank @@
+Normal rank
@@ Property / cites work @@
+On sparse sets in NP-P
@@ Property / cites work: On sparse sets in NP-P / rank @@
+Normal rank
@@ Property / cites work @@
+Sparse sets in NP-P: EXPTIME versus NEXPTIME
@@ Property / cites work: Sparse sets in NP-P: EXPTIME versus NEXPTIME / rank @@
+Normal rank
@@ Property / cites work @@
+NONDETERMINISTICALLY SELECTIVE SETS
@@ Property / cites work: NONDETERMINISTICALLY SELECTIVE SETS / rank @@
+Normal rank
@@ Property / cites work @@
+Computing Solutions Uniquely Collapses the Polynomial Hierarchy
+Normal rank
@@ Property / cites work @@
+Optimal advice
@@ Property / cites work: Optimal advice / rank @@
+Normal rank
@@ Property / cites work @@
+Q2769034
@@ Property / cites work: Q2769034 / 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 @@
+Q4273947
@@ Property / cites work: Q4273947 / rank @@
+Normal rank
@@ Property / cites work @@
+Relativization of questions about log space computability
+Normal rank
@@ Property / cites work @@
+A comparison of polynomial time reducibilities
@@ Property / cites work: A comparison of polynomial time reducibilities / rank @@
+Normal rank
@@ Property / cites work @@
+Symmetric space-bounded computation
@@ Property / cites work: Symmetric space-bounded computation / rank @@
+Normal rank
@@ Property / cites work @@
+Q4281499
@@ Property / cites work: Q4281499 / rank @@
+Normal rank
@@ Property / cites work @@
+A note on the graph isomorphism counting problem
@@ Property / cites work: A note on the graph isomorphism counting problem / rank @@
+Normal rank
@@ Property / cites work @@
+Q5585195
@@ Property / cites work: Q5585195 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4808678
@@ Property / cites work: Q4808678 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4234059
@@ Property / cites work: Q4234059 / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial-Time Membership Comparable Sets
@@ Property / cites work: Polynomial-Time Membership Comparable Sets / rank @@
+Normal rank
@@ Property / cites work @@
+Q4298260
@@ Property / cites work: Q4298260 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximate formulas for some functions of prime numbers
+Normal rank
@@ Property / cites work @@
+On the density of families of sets
@@ Property / cites work: On the density of families of sets / rank @@
+Normal rank
@@ Property / cites work @@
+P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
+Normal rank
@@ Property / cites work @@
+On membership comparable sets
@@ Property / cites work: On membership comparable sets / rank @@
+Normal rank
@@ Property / cites work @@
+On polynomial-time truth-table reducibility of intractable sets to P-selective sets
+Normal rank
@@ Property / cites work @@
+Q4036702
@@ Property / cites work: Q4036702 / rank @@
+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 @@
+Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets
+Normal rank
@@ Property / cites work @@
+On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
+Normal rank
@@ Property / DOI @@
+.1016/J.JCSS.2004.03.003
@@ Property / DOI: 10.1016/J.JCSS.2004.03.003 / rank @@
+Normal rank