Notes on polynomial levelability
From MaRDI portal
Publication:1119389
DOI10.1007/BF02006060zbMath0671.68011MaRDI QIDQ1119389
Publication date: 1988
Published in: Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)
Cites Work
- On one-one polynomial time equivalence relations
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- A Note on Sparse Complete Sets
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- Nonlevelable sets and immune sets in the accepting density hierarchy inNP
- Optimal Approximations and Polynomially Levelable Sets
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Complete sets and closeness to complexity classes
This page was built for publication: Notes on polynomial levelability
