Separating NE from some nonuniform nondeterministic complexity classes (Q652627): Difference between revisions

@@ 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.1007/s10878-010-9327-5
+Normal rank
@@ Property / OpenAlex ID @@
+W1981717863
@@ Property / OpenAlex ID: W1981717863 / rank @@
+Normal rank
@@ Property / cites work @@
+On Isomorphisms and Density of $NP$ and Other Complete Sets
+Normal rank
@@ Property / cites work @@
+On sets Turing reducible to p-selective sets
@@ Property / cites work: On sets Turing reducible to p-selective sets / rank @@
+Normal rank
@@ Property / cites work @@
+Sparse hard sets for P: Resolution of a conjecture of Hartmanis
+Normal rank
@@ Property / cites work @@
+A hierarchy for nondeterministic time complexity
@@ Property / cites work: A hierarchy for nondeterministic time complexity / rank @@
+Normal rank
@@ Property / cites work @@
+On lower bounds of the closeness between complexity classes
+Normal rank
@@ Property / cites work @@
+With Quasilinear Queries EXP Is Not Polynomial Time Turing Reducible to Sparse Sets
+Normal rank
@@ Property / cites work @@
+Complete Problems and Strong Polynomial Reducibilities
+Normal rank
@@ Property / cites work @@
+The complexity theory companion
@@ Property / cites work: The complexity theory companion / rank @@
+Normal rank
@@ Property / cites work @@
+Theory of semi-feasible algorithms
@@ Property / cites work: Theory of semi-feasible algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Computability and complexity theory
@@ Property / cites work: Computability and complexity theory / rank @@
+Normal rank
@@ Property / cites work @@
+Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
+Normal rank
@@ Property / cites work @@
+Separating classes in the exponential-time hierarchy from classes in PH
+Normal rank
@@ Property / cites work @@
+On the reducibility of sets inside NP to sets with low information content
+Normal rank
@@ Property / cites work @@
+Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
+Normal rank
@@ Property / cites work @@
+On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
+Normal rank