Sparse selfreducible sets and nonuniform lower bounds (Q1755786): Difference between revisions

@@ Property / author @@
-Q343857
@@ Property / author: Q343857 / rank @@
-Normal rank
@@ Property / author @@
+Nikolai K. Vereshchagin
@@ Property / author: Nikolai K. Vereshchagin / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2809558868
@@ Property / OpenAlex ID: W2809558868 / rank @@
+Normal rank
@@ Property / cites work @@
+Quasi-linear truth-table reductions to \(p\)-selective sets
+Normal rank
@@ Property / cites work @@
+Q4039803
@@ Property / cites work: Q4039803 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4258566
@@ Property / cites work: Q4258566 / rank @@
+Normal rank
@@ Property / cites work @@
+On Isomorphisms and Density of $NP$ and Other Complete Sets
+Normal rank
@@ Property / cites work @@
+Approximable sets
@@ Property / cites work: Approximable sets / rank @@
+Normal rank
@@ Property / cites work @@
+\(p\)-selective self-reducible sets: a new characterization of P
+Normal rank
@@ Property / cites work @@
+Mathematical Foundations of Computer Science 2005
@@ Property / cites work: Mathematical Foundations of Computer Science 2005 / 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 @@
+On Circuit-Size Complexity and the Low Hierarchy in NP
+Normal rank
@@ Property / cites work @@
+Self-reducible sets of small density
@@ Property / cites work: Self-reducible sets of small density / rank @@
+Normal rank
@@ Property / cites work @@
+Separating classes in the exponential-time hierarchy from classes in PH
+Normal rank
@@ Property / cites work @@
+Polynomial-Time Membership Comparable Sets
@@ Property / cites work: Polynomial-Time Membership Comparable Sets / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
+Normal rank
@@ Property / cites work @@
+Q4298260
@@ Property / cites work: Q4298260 / rank @@
+Normal rank
@@ Property / cites work @@
+P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
+Normal rank
@@ Property / cites work @@
+Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
+Normal rank
@@ Property / cites work @@
+Pseudorandomness for approximate counting and sampling
+Normal rank
@@ Property / cites work @@
+Relativized circuit complexity
@@ Property / cites work: Relativized circuit complexity / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:1755786