scientific article; zbMATH DE number 1962843

MaRDI QIDQ4418680zbMATH OpenFDO

Authors Harry Buhrman, Richard Chang, Lance Fortnow

Publication date 11 August 2003

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2607/26070547.htm

Mathematics Subject Classification ID

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

Recommendations

• Complexity-Restricted Advice Functions
• Bounding the complexity of advice functions
• Consequences of the provability of NP ⊆ P/poly
• From logarithmic advice to single-bit advice
• Logarithmic advice classes

Cited in

(7)

• Advice to the relevantist policeman
• From logarithmic advice to single-bit advice
• A Tight Karp-Lipton Collapse Result in Bounded Arithmetic
• Nondeterministic Instance Complexity and Proof Systems with Advice
• A GOOD ADVISOR
• Consequences of the provability of NP ⊆ P/poly
• Proof systems that take advice

This page was built for publication:

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