4 ms·

> 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

by 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.

ux266478 2mo ago
The point that what gets published adapts to the state of the art is fair. Personally I think its adaptations for ANNs and interaction nets are more interesting than the quantum ones. Once it has to account for the topology of the computer, or deal with non-atomic and continuous substrates, it changes a little bit. But this is orthogonal. The point wasn't that you can't make it adapt, I hope it doesn't come across like I'm dismissing the field and its importance. What I'm trying to say rather specifically is that it's not it's not about studying the nature of computation. It lives at a different level of theory than that. It might just be a disagreement on the article being used. I think it would be fair to say it studies a nature, just not the nature, but that would be true of all fields of CS.
- pron 2mo ago
  I would say that it very much is about the nature of computation, but computation itself has always been tied to the physical. The physicality (even hypothetical physicality) is exactly what separates theoretical computer science from pure mathematics. Even the two primary resources that complexity measures - time and space - are tied to physical quantities.
  - ux266478 2mo ago
    The distinction is certainly a fair one to make. The etymological root of computation is "done with mental labor", by way of "to clean a financial ledger" (although weirdly, this isn't the real root. Putare is botancial pruning. Computare is a metaphor created after it spent some time on the semantic treadmill.) Grounding it to the physical is perfectly sane, because that's historically how it's been used. That being said, a counterargument to press against this is that complexity theory doesn't restrict itself to physical or hypothetical physicality in its totality. As I mentioned, there are swaths of complexity theory work which bound quite far afield. The higher orders of the field are decidedly not-physical at all (and pedantically, hypercomputation isn't strictly computation). Of course even beyond this, we're still not studying the nature of computation, we're studying the cost. While you might say that of course these things are tied thanks to physicality (I wouldn't agree that they're equivalent on this basis, but I don't think that's an interesting semantic argument), I did also mention Landauer's principle being plausibly challenged, which is further problematic for conflating the two. Computation being reversible where entropy isn't doesn't explode complexity theory, but it does drive a wedge between information in a computer-sense and information in a thermodynamics sense. At that point, we don't have the claim in the first place, it's just a false friend. Something to consider.
    - pron 2mo ago
      I'm not saying computational complexity restricts itself to the physically realisable, I said it's tied to it and so there will be more papers on models that have some correspondence with physical reality. > we're still not studying the nature of computation, we're studying the cost That is one way of studying the nature of things, sort of like the use of the Hamiltonian in physics, especially if you're interested in problems and classes of problems, and their broad similarities and differences via reductions, rather than in specific computations. > The higher orders of the field are decidedly not-physical at all (and pedantically, hypercomputation isn't strictly computation). Hypercomputation isn't really a big part of the main thrust of complexity theory, but (computable) oracles do very much play an important role in complexity theory, even in its lowest complexity classes, such as in the relativisation barrier, which shows that some proof techniques cannot separate P from NP. > I did also mention Landauer's principle being plausibly challenged, That's not complexity theory, at least not the standard theory, which treats time and space (or circuit size) more abstractly than concrete physics. There are, however, theoretical reversible models, just note that they don't yield different "classic" deterministic complexity classes (i.e. they do not yield exponential differences).

by pron 2mo ago

ux266478 2mo ago

The point that what gets published adapts to the state of the art is fair. Personally I think its adaptations for ANNs and interaction nets are more interesting than the quantum ones. Once it has to account for the topology of the computer, or deal with non-atomic and continuous substrates, it changes a little bit. But this is orthogonal. The point wasn't that you can't make it adapt, I hope it doesn't come across like I'm dismissing the field and its importance. What I'm trying to say rather specifically is that it's not it's not about studying the nature of computation. It lives at a different level of theory than that. It might just be a disagreement on the article being used. I think it would be fair to say it studies a nature, just not the nature, but that would be true of all fields of CS.

pron 2mo ago
I would say that it very much is about the nature of computation, but computation itself has always been tied to the physical. The physicality (even hypothetical physicality) is exactly what separates theoretical computer science from pure mathematics. Even the two primary resources that complexity measures - time and space - are tied to physical quantities.
- ux266478 2mo ago
  The distinction is certainly a fair one to make. The etymological root of computation is "done with mental labor", by way of "to clean a financial ledger" (although weirdly, this isn't the real root. Putare is botancial pruning. Computare is a metaphor created after it spent some time on the semantic treadmill.) Grounding it to the physical is perfectly sane, because that's historically how it's been used. That being said, a counterargument to press against this is that complexity theory doesn't restrict itself to physical or hypothetical physicality in its totality. As I mentioned, there are swaths of complexity theory work which bound quite far afield. The higher orders of the field are decidedly not-physical at all (and pedantically, hypercomputation isn't strictly computation). Of course even beyond this, we're still not studying the nature of computation, we're studying the cost. While you might say that of course these things are tied thanks to physicality (I wouldn't agree that they're equivalent on this basis, but I don't think that's an interesting semantic argument), I did also mention Landauer's principle being plausibly challenged, which is further problematic for conflating the two. Computation being reversible where entropy isn't doesn't explode complexity theory, but it does drive a wedge between information in a computer-sense and information in a thermodynamics sense. At that point, we don't have the claim in the first place, it's just a false friend. Something to consider.
  - pron 2mo ago
    I'm not saying computational complexity restricts itself to the physically realisable, I said it's tied to it and so there will be more papers on models that have some correspondence with physical reality. > we're still not studying the nature of computation, we're studying the cost That is one way of studying the nature of things, sort of like the use of the Hamiltonian in physics, especially if you're interested in problems and classes of problems, and their broad similarities and differences via reductions, rather than in specific computations. > The higher orders of the field are decidedly not-physical at all (and pedantically, hypercomputation isn't strictly computation). Hypercomputation isn't really a big part of the main thrust of complexity theory, but (computable) oracles do very much play an important role in complexity theory, even in its lowest complexity classes, such as in the relativisation barrier, which shows that some proof techniques cannot separate P from NP. > I did also mention Landauer's principle being plausibly challenged, That's not complexity theory, at least not the standard theory, which treats time and space (or circuit size) more abstractly than concrete physics. There are, however, theoretical reversible models, just note that they don't yield different "classic" deterministic complexity classes (i.e. they do not yield exponential differences).