Complexity-Restricted Advice Functions

DOI10.1137/S0097539791200351zbMath0804.68049OpenAlexW2075406496MaRDI QIDQ4291556

Thomas Thierauf, Johannes Köbler

Publication date: 10 May 1994

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

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

zbMATH Keywords

Boolean hierarchyrelativizationtruth-table reducibilityadvice classesnonuniform complexity classesoptimization functionsrestricted oracle accesssparse NP sets

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Optimal advice ⋮ SELF-SPECIFYING MACHINES ⋮ Some structural properties of SAT ⋮ Bounded queries, approximations, and the Boolean hierarchy