4 ms·

1. The study of complexity classes isn't intended to dissuade people from writing certain programs. It's intended to understand the nature and theoretical limit

by pron 2mo ago

1. The study of complexity classes isn't intended to dissuade people from writing certain programs. It's intended to understand the nature and theoretical limits of computation. As far as practice goes, it can be used to show where heuristics are needed. Saying it's overrated is like saying calculus is overrated because most people don't need to use it every day. And BTW, many important problems are in classes believed to be way harder than NP (i.e. NP-complete is the easiest of the hard famous complexity classes). E.g., I've seen some people brag about some configuration language being easy to mechanically analyse because it's not Turing-complete, while in fact it's at least PSPACE-hard to analyse. 2. When there's some large set of instances of some NP-hard problem that are tractably solvable in practice (like SAT), the importance of that is that there's some non-NP-hard subset here. Indeed, SAT is FPT (fixed parameter tractable [1]), an "easier" type of NP, for which decomposition can help. In contrast, graph colouring is thought to not be FPT. [1]: https://en.wikipedia.org/wiki/Parameterized_complexity https://en.wikipedia.org/wiki/Parameterized_complexity

ux266478 2mo ago
> It's intended to understand the nature and theoretical limits of computation. Not in a general sense, at least for standard complexity theory. It only deals with a very specific model of computation. Anyone with a sufficiently solid grasp of metamathematics intuitively understands that the distinction between solve and verify is nothing but a description of how badly matched our foundations are for the structure we're trying to view. ... This is the second time today I've posted about foundations like this.
- zero-sharp 2mo ago
  >Not in a general sense, at least for standard complexity theory. It only deals with a very specific model of computation. What is an example of a model of computation where complexity theory doesn't apply?
  - ux266478 2mo ago
    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
aaron695 2mo ago
[dead]
ragall 2mo ago
> Saying it's overrated is like saying calculus is overrated because most people don't need to use it every day. You should stop thinking by analogy. The article was showing the difference between mathematicians and engineers. For the mathematicians that created Computation Science, the only interesting solutions are complete solutions to general questions, whereas for engineers it's perfectly acceptable to eliminate some corner cases, thereby solving a reduced and simplified version of the general problem.
- pron 2mo ago
  > For the mathematicians that created Computation Science, the only interesting solutions are complete solutions to general questions Except that's not really true, which is the whole point of the finer computational classes. If many instances are far from the worst case, that tells you something interesting about the class, which is why we have things like parameterised complexity. People who think that the theory is only interested in the general case of the broad classes you learn as an undergrad are just not sufficiently familiar with the theory.
- saithound 2mo ago
  > The article was showing the difference between mathematicians and engineers. No. Many engineers AND mathematicians worked for a long time to get us to a stage where Amazon can solve a billion SMT problems a day. To contribute, all of them had to understand the theory this article calls overrated.
  - ragall 2mo ago
    Some mathematicians certainly did, but there's a very large undercurrent in CS, as well as Mathematics more in general, of utter disinterest for applications as well as the idea that the more general a solution, the more "worthy" it is. That was really obvious from the words of the professor cited in the article.
    - dizzant 2mo ago
      Would you disagree that, given the choice, a solution to every problem is strictly better than a solution so only some problems?
eru 2mo ago
> E.g., I've seen some people brag about some configuration language being easy to mechanically analyse because it's not Turing-complete, while in fact it's at least PSPACE-hard to analyse. Isn't even just the question of minimising the length of a regular expression PSPACE-hard or so?
pyrale 2mo ago
> E.g., I've seen some people brag about some configuration language being easy to mechanically analyse because it's not Turing-complete, while in fact it's at least PSPACE-hard to analyse. I don't get your point here. What analysis are you talking about? I believe the claim usually made about non-turing-complete languages is that it is possible to prove specific properties with little to no calculations, that would be otherwise hard to calculate. For instance, the time needed to determine that an Idris program will eventually stop is litteraly 0 seconds.
- pron 2mo ago
  > I don't get your point here. What analysis are you talking about? Determining any kind of non-trivial property (i.e. a property that isn't true for all or none of the programs in the language). > I believe the claim usually made about non-turing-complete languages is that it is possible to prove specific properties with little to no calculations, that would be otherwise hard to calculate. For instance, the time needed to determine that an Idris program will eventually stop is litteraly 0 seconds. It's not the non-Turing-completeness that makes that practical. Let's take your example of Idris: 1. If a program's termination is hard to determine, then it will be hard to write it in Idris. I.e., the effort isn't gone, it's just shifted elsewhere. And if the program is easy to write in Idris, then its termination is also easy to prove in other languages (Idris effectively requires you to write a proof of termination, but you can write the proof for any language). 2. The importance of this is not as high as you think. For example, we can trivially rewrite all of the world's software in an always-terminating language (so not-Turing-complete), by changing the semantics of all programs to terminate after 2^100 steps. This will not affect the behaviour of any software, and you can see why it also won't make determining any of their properties of interest any easier. So yes, Idris makes termination a trivial property for Idris programs, but it doesn't make the effort of determining whether an algorithm terminates or not easier (you just have to do it _while_ you're writing the program instead of after), and it doesn't, by itself, make any other property (which remains non-trivial) easier, such as "does the program terminate in fewer than 2^100 steps?"
  - pyrale 2mo ago
    > Idris effectively requires you to write a proof of termination, but you can write the proof for any language That is the benefit of non-turing complete languages, though. Or, in general, the point of languages with useful type systems. Writing the proof is not trivial, but languages like Rust or Idris make it simple because they force correctness early in the coding process.
fcholf 2mo ago
I agree with 1 but: > 2. When there's some large set of instances of some NP-hard problem that are tractably solvable in practice (like SAT), the importance of that is that there's some non-NP-hard subset here. Indeed, SAT is FPT (fixed parameter tractable [1]), an "easier" type of NP, for which decomposition can help. In contrast, graph colouring is thought to not be FPT. Sorry but I need to clarify here. "SAT is FPT" does not mean anything. FPT only makes sense when you tell what is the *parameter*. Every problem is FPT when parametrized by the input size so graph colouring and SAT are FPT wrt to the size of the input (the graph and the formula respectively). What you meant: graph colouring parametrized by the number of colours is unlikely to be FPT (since it is W[1]-hard). SAT is FPT for many parameters such as treewidth (of the formula). Oh, and btw, graph colouring is also FPT when parametrized by treewidth (of the graph).
- pron 2mo ago
  I take your correction re graph colouring, but the rest is pointlessly pedantic (especially "FPT in the length", which is trivial and so typically excluded from the definition). Now, I don't know if SAT being FPT (in a parameter of interest) has anything to do with the surprising ease of many "natural" instances (even with many variables), but my point was that when many instances are easy, that doesn't mean that the class is irrelevant, it just means it's more interesting (as there's obviously a tractable subclass, albeit one we haven't yet defined succinctly).
  - fcholf 2mo ago
    Late answer but I need to be pointlessly pedantic again, because it is apparently what it is called to correct something that does not make sense. That said, I agree with your way of reformulating your point. To first address the pedanticness: "FPT in the length of the input" is not excluded from the definition of FPT even if it is not an interesting case. Excluding these cases from the definition would make the theory uselessly complicated. Now, back to the point of my first comment. It was mostly to show that you cannot use "FPTness" as an argument to justify that SAT is "easier" than graph colouring. I used "length of the input" to give an easy counter example, to show that FPT is not "an easier type of NP". It never has been. It is a way of understanding and measuring the complexity of the problem finely, to isolate hard parts of the input from the rest. What the W[1]-hardness of graph colouring parametrised by the number of colours tells you is that this parameter is not a relevant parameter and that's it. Graph colouring is FPT for many relevant graph parameters such as treewidth, clique-width (SAT is not even FPT wrt clique-width, but again, you cannot really use the concept of FPT to compare problems). You will have a hard time using theory to justify that SAT is easier than any other NP-complete problem, because from the theory point of view, it is the hardest NP-problem you can get. Unless something unexpected happens in complexity theory, SAT cannot be efficiently solved in randomized time, SAT cannot be solved in sub-exponential time, SAT is complete under parsimonious reductions so you can basically take any NP-complete problem and build a CNF formula whose models are isomorphic to the solutions of the original instance etc. The success of SAT solvers does not mean that SAT is easier than other NP-hard problem. It means that many combinatorial problems we need to solve in practice are "simple enough" that using the incredibly optimized smart way of bruteforcing the solution with a CDCL SAT solver is good enough. Now, take a cryptographic instance, translate it into a CNF formula and call a SAT solver, I doubt it will shine. Despite many attempts, this behaviour has never clearly be explained by the fact that the complexity of CDCL is FPT wrt a parameter that is small in industrial instances.

by pron 2mo ago

ux266478 2mo ago

> It's intended to understand the nature and theoretical limits of computation. Not in a general sense, at least for standard complexity theory. It only deals with a very specific model of computation. Anyone with a sufficiently solid grasp of metamathematics intuitively understands that the distinction between solve and verify is nothing but a description of how badly matched our foundations are for the structure we're trying to view. ... This is the second time today I've posted about foundations like this.

zero-sharp 2mo ago
>Not in a general sense, at least for standard complexity theory. It only deals with a very specific model of computation. What is an example of a model of computation where complexity theory doesn't apply?
- ux266478 2mo ago
  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

aaron695 2mo ago

[dead]

ragall 2mo ago

> Saying it's overrated is like saying calculus is overrated because most people don't need to use it every day. You should stop thinking by analogy. The article was showing the difference between mathematicians and engineers. For the mathematicians that created Computation Science, the only interesting solutions are complete solutions to general questions, whereas for engineers it's perfectly acceptable to eliminate some corner cases, thereby solving a reduced and simplified version of the general problem.

pron 2mo ago
> For the mathematicians that created Computation Science, the only interesting solutions are complete solutions to general questions Except that's not really true, which is the whole point of the finer computational classes. If many instances are far from the worst case, that tells you something interesting about the class, which is why we have things like parameterised complexity. People who think that the theory is only interested in the general case of the broad classes you learn as an undergrad are just not sufficiently familiar with the theory.
saithound 2mo ago
> The article was showing the difference between mathematicians and engineers. No. Many engineers AND mathematicians worked for a long time to get us to a stage where Amazon can solve a billion SMT problems a day. To contribute, all of them had to understand the theory this article calls overrated.
- ragall 2mo ago
  Some mathematicians certainly did, but there's a very large undercurrent in CS, as well as Mathematics more in general, of utter disinterest for applications as well as the idea that the more general a solution, the more "worthy" it is. That was really obvious from the words of the professor cited in the article.
  - dizzant 2mo ago
    Would you disagree that, given the choice, a solution to every problem is strictly better than a solution so only some problems?

eru 2mo ago

pyrale 2mo ago

> E.g., I've seen some people brag about some configuration language being easy to mechanically analyse because it's not Turing-complete, while in fact it's at least PSPACE-hard to analyse. I don't get your point here. What analysis are you talking about? I believe the claim usually made about non-turing-complete languages is that it is possible to prove specific properties with little to no calculations, that would be otherwise hard to calculate. For instance, the time needed to determine that an Idris program will eventually stop is litteraly 0 seconds.

pron 2mo ago
> I don't get your point here. What analysis are you talking about? Determining any kind of non-trivial property (i.e. a property that isn't true for all or none of the programs in the language). > I believe the claim usually made about non-turing-complete languages is that it is possible to prove specific properties with little to no calculations, that would be otherwise hard to calculate. For instance, the time needed to determine that an Idris program will eventually stop is litteraly 0 seconds. It's not the non-Turing-completeness that makes that practical. Let's take your example of Idris: 1. If a program's termination is hard to determine, then it will be hard to write it in Idris. I.e., the effort isn't gone, it's just shifted elsewhere. And if the program is easy to write in Idris, then its termination is also easy to prove in other languages (Idris effectively requires you to write a proof of termination, but you can write the proof for any language). 2. The importance of this is not as high as you think. For example, we can trivially rewrite all of the world's software in an always-terminating language (so not-Turing-complete), by changing the semantics of all programs to terminate after 2^100 steps. This will not affect the behaviour of any software, and you can see why it also won't make determining any of their properties of interest any easier. So yes, Idris makes termination a trivial property for Idris programs, but it doesn't make the effort of determining whether an algorithm terminates or not easier (you just have to do it _while_ you're writing the program instead of after), and it doesn't, by itself, make any other property (which remains non-trivial) easier, such as "does the program terminate in fewer than 2^100 steps?"
- pyrale 2mo ago
  > Idris effectively requires you to write a proof of termination, but you can write the proof for any language That is the benefit of non-turing complete languages, though. Or, in general, the point of languages with useful type systems. Writing the proof is not trivial, but languages like Rust or Idris make it simple because they force correctness early in the coding process.

fcholf 2mo ago

I agree with 1 but: > 2. When there's some large set of instances of some NP-hard problem that are tractably solvable in practice (like SAT), the importance of that is that there's some non-NP-hard subset here. Indeed, SAT is FPT (fixed parameter tractable [1]), an "easier" type of NP, for which decomposition can help. In contrast, graph colouring is thought to not be FPT. Sorry but I need to clarify here. "SAT is FPT" does not mean anything. FPT only makes sense when you tell what is the *parameter*. Every problem is FPT when parametrized by the input size so graph colouring and SAT are FPT wrt to the size of the input (the graph and the formula respectively). What you meant: graph colouring parametrized by the number of colours is unlikely to be FPT (since it is W[1]-hard). SAT is FPT for many parameters such as treewidth (of the formula). Oh, and btw, graph colouring is also FPT when parametrized by treewidth (of the graph).

pron 2mo ago
I take your correction re graph colouring, but the rest is pointlessly pedantic (especially "FPT in the length", which is trivial and so typically excluded from the definition). Now, I don't know if SAT being FPT (in a parameter of interest) has anything to do with the surprising ease of many "natural" instances (even with many variables), but my point was that when many instances are easy, that doesn't mean that the class is irrelevant, it just means it's more interesting (as there's obviously a tractable subclass, albeit one we haven't yet defined succinctly).
- fcholf 2mo ago
  Late answer but I need to be pointlessly pedantic again, because it is apparently what it is called to correct something that does not make sense. That said, I agree with your way of reformulating your point. To first address the pedanticness: "FPT in the length of the input" is not excluded from the definition of FPT even if it is not an interesting case. Excluding these cases from the definition would make the theory uselessly complicated. Now, back to the point of my first comment. It was mostly to show that you cannot use "FPTness" as an argument to justify that SAT is "easier" than graph colouring. I used "length of the input" to give an easy counter example, to show that FPT is not "an easier type of NP". It never has been. It is a way of understanding and measuring the complexity of the problem finely, to isolate hard parts of the input from the rest. What the W[1]-hardness of graph colouring parametrised by the number of colours tells you is that this parameter is not a relevant parameter and that's it. Graph colouring is FPT for many relevant graph parameters such as treewidth, clique-width (SAT is not even FPT wrt clique-width, but again, you cannot really use the concept of FPT to compare problems). You will have a hard time using theory to justify that SAT is easier than any other NP-complete problem, because from the theory point of view, it is the hardest NP-problem you can get. Unless something unexpected happens in complexity theory, SAT cannot be efficiently solved in randomized time, SAT cannot be solved in sub-exponential time, SAT is complete under parsimonious reductions so you can basically take any NP-complete problem and build a CNF formula whose models are isomorphic to the solutions of the original instance etc. The success of SAT solvers does not mean that SAT is easier than other NP-hard problem. It means that many combinatorial problems we need to solve in practice are "simple enough" that using the incredibly optimized smart way of bruteforcing the solution with a CDCL SAT solver is good enough. Now, take a cryptographic instance, translate it into a CNF formula and call a SAT solver, I doubt it will shine. Despite many attempts, this behaviour has never clearly be explained by the fact that the complexity of CDCL is FPT wrt a parameter that is small in industrial instances.