alt Hacker News> Standard complexity theory focuses on answering questions when our substrate behaves like a Turing machine with multiple tapes.
This is not true. Complexity theory very much looks at complexity under different models (alphabet size, oracles, circuits). It's just that often (e.g. in the case of alphabets), there is a reduction of known complexity between two models.
> It quantifies that distance between prove and verify, but it doesn't study the set of all those distances and how they arise.
This is also not true (https://en.wikipedia.org/wiki/Proof_complexity).
> there is a reduction of known complexity between two models.
Every single time I've seen, for example, the lambda calculus be assigned cost semantics, it usually looks like what you would expect out of a Turing machine's simulation of it. Often times, they're explicit about it: https://www.sciencedirect.com/science/article/pii/S030439750...
For me, I can't accept that this is the criteria of "reasonable." Especially not for abstract theory.
I did try to indicate I'm mostly talking about standard complexity theory, the stuff you'd encounter on the surface level of the field. I'm not an expert in CT, but I do know enough to know what Landauer's principle is (and that it's been plausibly challenged.) I also know there's some crazy stuff in there, like descriptive complexity theory's link between Existential SOL and NP-Complexity.
> This is also not true (https://en.wikipedia.org/wiki/Proof_complexity).
Do you have any complexity theory papers that deal with this specifically? I've only ever seen that kind of work done in mathematical logic. Genuine interest in reading the CT approach.