Weak lower bounds on resource-bounded compression imply strong separations of complexity classes.

Dylan M. McKay Cody D. Murray R. Ryan Williams

Published in: STOC (2019)

Keyphrases

resource bounded
lower bound
worst case
information gathering
upper bound
autonomous agents
meta level
image compression
decision problems
computational complexity
multiscale
object level
recursive functions