5 ms·

Standard complexity theory focuses on answering questions when our substrate behaves like a Turing machine with multiple tapes. Consider it like this, if the a

Standard complexity theory focuses on answering questions when our substrate behaves like a Turing machine with multiple tapes. Consider it like this, if the answer is in our system's axioms, we don't have to do anything. In a trivial sense that means we're just given the answer table, but it's also true if our substrate matches the model of computation its simulating. IE for an SLD-Resolution machine, running an SLD-Resolution object language, unification is worst case O(1). This is a degenerate case of course, but it's an example of something that's not realizable on a Turing machine's semantics where the worst case is in... EXPTIME? It's not great. The more we treat our substrate like building blocks, and less like a holistic oracle, that changes our complexity landscape. Complexity theory was never about studying that whole landscape. You might want to say CT is pragmatic and focused on realizable machines. There are two problems with that: 1. There's nothing special with the baseline used for complexity theory other than its familiarity. Reality is our ultimate substrate. The universe is not Turing tape. There is absolutely no serious basis upon which an argument against substrates can be made, especially with how little we know and understand about the universe. 2. Complexity theory isn't so pragmatic to only study the finitely bounded, which also changes everything. There seems a very tight upper bound on information in the universe. Even studying up to it as a limit is decidedly not pragmatic in the slightest. This is perfectly fine of course, the problem only enters in when we want to be "pragmatic" on some things, but not others. I also want to clarify: There are higher orders of complexity theory that have generalized a lot of its concepts, even into hypercomputation which is cool, but then there's another problem I didn't mention. Complexity theory still isn't about what he said. It quantifies that distance between prove and verify, but it doesn't study the set of all those distances and how they arise. It just quantifies them one at a time and has only a limited number of things to say beyond that. What he described is simply mathematical logic.

inigyou 2mo ago
Isn't complexity theory usual based on a random-access model, not any kind of Turing machine?
- ux266478 2mo ago
  MT Turing machines aren't really all that different. Or from pointer machines for that matter. They map nicely together.
- deleted 2mo ago
  [deleted]
pron 2mo 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 https://en.wikipedia.org/wiki/Proof_complexity).
- ux266478 2mo ago
  > 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/S0304397508000583 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 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.
  - pron 2mo ago
    > it usually looks like what you would expect out of a Turing machine's simulation of it You could assign it any cost model you want. Often this doesn't make a difference (as speedup theorems and other "distracting details" mean that most classes are intended to be separated by exponentials), but it is true that people are typically more interested in cost models that are more relevant to the physical universe (although number of reductions is very much the cost of focus in proof complexity). Indeed, relevant discoveries in physics yield corresponding computational complexity research, as in the case of quantum complexity (https://en.wikipedia.org/wiki/Quantum_complexity_theory https://en.wikipedia.org/wiki/Quantum_complexity_theory). > Do you have any complexity theory papers that deal with this specifically? A Google Scholar search for "proof complexity" will show you many papers as well as a number of books.
adrianN 2mo ago
We actually understand quite a bit about the universe and the kinds of computers we can build. People also think about computers in speculative physics scenarios, eg closed timelike curves can be used to solve pspace complete problems. I don’t think you can plausibly argue that complexity theory‘s base assumptions are a bad choice, at least not in the sense that you would assume that you can build exponentially more powerful computers in the physical universe. In fact, concerns about energy densities, limited amounts of matter, and the speed of light make it more difficult than typical machine models assume.

inigyou 2mo ago

Isn't complexity theory usual based on a random-access model, not any kind of Turing machine?

ux266478 2mo ago
MT Turing machines aren't really all that different. Or from pointer machines for that matter. They map nicely together.
deleted 2mo ago
[deleted]

pron 2mo 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 https://en.wikipedia.org/wiki/Proof_complexity).

ux266478 2mo ago
> 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/S0304397508000583 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 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.
- pron 2mo ago
  > it usually looks like what you would expect out of a Turing machine's simulation of it You could assign it any cost model you want. Often this doesn't make a difference (as speedup theorems and other "distracting details" mean that most classes are intended to be separated by exponentials), but it is true that people are typically more interested in cost models that are more relevant to the physical universe (although number of reductions is very much the cost of focus in proof complexity). Indeed, relevant discoveries in physics yield corresponding computational complexity research, as in the case of quantum complexity (https://en.wikipedia.org/wiki/Quantum_complexity_theory https://en.wikipedia.org/wiki/Quantum_complexity_theory). > Do you have any complexity theory papers that deal with this specifically? A Google Scholar search for "proof complexity" will show you many papers as well as a number of books.

adrianN 2mo ago

We actually understand quite a bit about the universe and the kinds of computers we can build. People also think about computers in speculative physics scenarios, eg closed timelike curves can be used to solve pspace complete problems. I don’t think you can plausibly argue that complexity theory‘s base assumptions are a bad choice, at least not in the sense that you would assume that you can build exponentially more powerful computers in the physical universe. In fact, concerns about energy densities, limited amounts of matter, and the speed of light make it more difficult than typical machine models assume.