Separating NE from Some Nonuniform Nondeterministic Complexity Classes
From MaRDI portal
Publication:5323096
DOI10.1007/978-3-642-02882-3_48zbMath1248.68204OpenAlexW1823436195MaRDI QIDQ5323096
Bin Fu, Liyu Zhang, Ang Sheng Li
Publication date: 23 July 2009
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-02882-3_48
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (1)
Cites Work
- On sets Turing reducible to p-selective sets
- Sparse complete sets for NP: solution of a conjecture of Berman and 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
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Computability and complexity theory
- Theory of semi-feasible algorithms
This page was built for publication: Separating NE from Some Nonuniform Nondeterministic Complexity Classes
