Complexity-Restricted Advice Functions

DOI10.1137/S0097539791200351MaRDI QIDQ4291556zbMATH OpenOpenAlexFDO

Authors Johannes Köbler, Thomas Thierauf

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

advice classesBoolean hierarchynonuniform complexity classesoptimization functionsrelativizationrestricted oracle accesssparse NP setstruth-table reducibility

Mathematics Subject Classification ID

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

Recommendations

• Logarithmic advice classes
• Restricted information from nonadaptive queries to NP
• Bounded Query Classes
• Bounding the complexity of advice functions

Cited in

(12)

• Logarithmic advice classes
• Some structural properties of SAT
• Bounded queries, approximations, and the Boolean hierarchy
• Bounding the complexity of advice functions
• Restricted information from nonadaptive queries to NP
• scientific article; zbMATH DE number 1962843 (Why is no real title available?)
• scientific article; zbMATH DE number 7311152 (Why is no real title available?)
• SELF-SPECIFYING MACHINES
• Real benefit of promises and advice
• Pinpointing computation with modular queries in the Boolean hierarchy
• Optimal advice
• Advice classes of parametrized tractability

This page was built for publication: Complexity-Restricted Advice Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4291556)