Separating NE from some nonuniform nondeterministic complexity classes
From MaRDI portal
Publication:652627
DOI10.1007/S10878-010-9327-5zbMath1254.90310OpenAlexW1981717863MaRDI QIDQ652627
Liyu Zhang, Bin Fu, Ang Sheng Li
Publication date: 15 December 2011
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-010-9327-5
Cites Work
- On sets Turing reducible to p-selective sets
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- Sparse hard sets for P: Resolution of a conjecture of Hartmanis
- Separating classes in the exponential-time hierarchy from classes in PH
- A hierarchy for nondeterministic time complexity
- On the reducibility of sets inside NP to sets with low information content
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- Complete Problems and Strong Polynomial Reducibilities
- On lower bounds of the closeness between complexity classes
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- With Quasilinear Queries EXP Is Not Polynomial Time Turing Reducible to Sparse Sets
- Computability and complexity theory
- The complexity theory companion
- Theory of semi-feasible algorithms
This page was built for publication: Separating NE from some nonuniform nondeterministic complexity classes
