On sparse oracles separating feasible complexity classes
From MaRDI portal
Publication:1111385
DOI10.1016/0020-0190(88)90176-7zbMath0658.68055MaRDI QIDQ1111385
Hemaspaandra, Lane A., Juris Hartmanis
Publication date: 1988
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/6547
Kolmogorov complexity; polynomial-time hierarchy; sparse oracle; classes of languages; P-printability; relativation; separating NP from P in worlds where \(P=NP\)
68Q25: Analysis of algorithms and problem complexity
Related Items