| ▲ | pron 37 minutes ago | |
> 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). | ||