Several commenters have remarked that the alt-complexity and K-complexity differ only up to a constant. I have now written a post where I write down a detailed proof of that classical result, which is known as the “coding theorem”.
I redacted this comment since it turns out my post is actually not precisely about the ALT-complexity. There’s nuance here I may go into in a future post.
Several commenters have remarked that the alt-complexity and K-complexity differ only up to a constant. I have now written a post where I write down a detailed proof of that classical result, which is known as the “coding theorem”.
I redacted this comment since it turns out my post is actually not precisely about the ALT-complexity. There’s nuance here I may go into in a future post.
I wrote a post incorporating these thoughts now.