With Quasilinear Queries EXP Is Not Polynomial Time Turing Reducible to Sparse Sets

DOI10.1137/S0097539792237188zbMath0845.68046OpenAlexW2010402642MaRDI QIDQ4857596

Bin Fu

Publication date: 24 January 1996

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539792237188

zbMATH Keywords

polynomial time Turing reductions

Mathematics Subject Classification ID

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

Related Items (2)

Dimension, halfspaces, and the density of hard sets ⋮ Separating NE from some nonuniform nondeterministic complexity classes

This page was built for publication: With Quasilinear Queries EXP Is Not Polynomial Time Turing Reducible to Sparse Sets