Hierarchies for semantic classes

DOI10.1145/1060590.1060642MaRDI QIDQ3581434zbMATH OpenOpenAlexFDO

Authors Rahul Santhanam, Luca Trevisan, Lance Fortnow

Publication date 16 August 2010

Published in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1060590.1060642

Mathematics Subject Classification ID

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

Cited in

(4)

• Randomness and intractability in Kolmogorov complexity
• Effective guessing has unlikely consequences
• Oblivious complexity classes revisited: lower bounds and hierarchies
• Time hierarchies for cryptographic function inversion with advice

This page was built for publication: Hierarchies for semantic classes

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