An interesting problem must have a description that fits in a brain, at least for now. Your description-length argument assumes arbitrarily large storage.
the smallest problem that cannot fit in a brain would be pretty interesting
the smallest problem that cannot fit in a brain would be pretty interesting