NE Is Not NP Turing Reducible to Nonexponentially Dense NP Sets

DOI10.1007/978-3-642-29344-3_32zbMath1353.68099arXiv1012.2394MaRDI QIDQ2894481

Bin Fu

Publication date: 29 June 2012

Published in: LATIN 2012: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1012.2394

Mathematics Subject Classification ID

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)