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.
> 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.
> 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.
> For the mathematicians that created Computation Science, the only interesting solutions are complete solutions to general questions
There is a bunch of research devoted to Polynomial Time Approximation Schemes (PTAS). Mathematicians also take part in it.
I did study a bit of complexity theory back in the day, and it does seem a bit theoretical, but not so long ago, I ran into an very prominent manifestation. To help someone, I had created a simple web page which also had an input field for the css that was applied directly to the page. To avoid flickering and weird effects because of malformed css, I wrote a regexp to check the CSS code. It's a very simple language, after all, and it didn't have to be perfect. It worked well, until at one point, a simple typo locked up Chrome for 1 minute 10 seconds. Parse time just jumped from less than 100ms to 70000ms by adding a single character. That's when you feel what exponential means.
I just want to point out that complexity theory isn't really about analysing the complexity of a particular algorithm (that's the subject of algorithm and data structure analysis, where students learn big-O notation), but about understanding the complexity of a problem independently of any algorithm (i.e. what problems couldn't be tractably solved by any algorithm).
> 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.
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.
I would to say I support that view. What is the purpose of modern science if not to discover truths you can apply universally? If you state: ‘this particular apple falls to the ground’ thats not a scientific discovery, there must be some general applicability.
There is an entire field of static analysis that is dedicated to practically solving undecidable problems.
Would you disagree that, given the choice, a solution to every problem is strictly better than a solution so only some problems?
No. Because for let’s say the halting problem the general case says it’s unsolvable, but each specific case is solvable.
1. Not all specific cases are solvable.
2. That the worst-case is very hard usually tells you that many instances will be hard (unless you discover an easy subclass), as is the case here. And when many "natural" instances are easy, that means that the problem is more interesting than perhaps previously thought, and it requires and receives more research, not less. If most instances are near the worst case, it means you know all there is to know about the problem; when they're not, it means there's more to study.
Can you give a specific finite program which is undecidable?
A program that enumerates all theorems in ZFC and stops when it proves a contradiction (e.g. true = false). Encoding a program that is equivalent to that directly as a Turing Machine in merely 748 states: https://www.scottaaronson.com/papers/bb.pdf (meaning that we cannot prove an upper bound on the 748th Busy-Beaver number, but there are probably even smaller undecidable TMs).
But my favourite example (shown here in Java) demonstrates the difficulty of analysing simple, realistic programs without necessarily being undecidable:
Even in this case where even the input space is finite (and so everything here is definitely decidable), we simply don't yet know whether there is some x for which foo(x) throws, let alone if we made the input unbounded by using BigInteger instead of long.Yes I disagree, because the algorithm to solve every problem takes longer to run than the remaining age of the universe.
You have clearly not encountered theoretical computer scientists. They love to create all kinds of complexity classes and theorems to capture things like heuristics and approximation algorithms and other things which work in practice but not theory.
In fact that’s a big research thrust right now, to understand why many real-world SAT instances are solvable quickly while others are not, and where the threshold between them lies
I studied mathematics, and can attest that the attitude of the professor mentioned in the article is very representative of an older generation of mathematicians. Maybe the younger ones are different.
I also studied mathematics, and I can tell you that this was not my experience.
Rather, if a problem is NP-complete/NP-hard it means that we cannot expect a general fast algorithms for exactly this problem (in other words: more mathematics is required, which mathematicians of course love).
But it is absolutely known that there exist other strategies:
- Develop algorithms that work well in practice and make understanding why they work so well in practice your career.
- Find out whether there exists something that makes the instances that occur in practice different from those instances that were used in the proof that the problem is NP-complete/-hard.
- For optimization problems: develop some fast algorithm which guarantees some approximation factor.
It't not a matter of generations. There are plenty of old mathematicians who are very interested in applications and plenty of young mathematicians who are only interested in generalized abstract nonsense. It's more of a difference in personality that will always be there.
> 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?
> 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.
> 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?"
> 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.
> That is the benefit of non-turing complete languages, though.
That's simply untrue. You can write arbitrary proofs about programs in Turing-complete languages, too. In fact, most formal proofs are of programs written in Turing-complete languages.
> but languages like Rust or Idris make it simple because they force correctness early in the coding process.
Rust doesn't actually let you do that, though. In terms of the expressive power of proof, it is far closer to C than to Idris (in fact, from Idris's vantage point, Rust is almost indistinguishable from C).
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).
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).
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.
> You will have a hard time using theory to justify that SAT is easier than any other NP-complete problem
"Easier" perhaps isn't the right word (in terms of reducibility, it certainly isn't), but FPT is just a way to demonstrate that NP-complete problems can be different from each other in ways that matter (with respect to "natural" instances).
> Now, take a cryptographic instance, translate it into a CNF formula and call a SAT solver, I doubt it will shine.
Exactly. And researchers are very much interested in these differences that arise in natural instances and are hidden by "crude" reduction.
[dead]
> 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.
>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?
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.
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.
> 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.
> 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).
> 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.
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.
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.
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.
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).
Again, all fair. To simplify, my points are to demonstrate a confounding nuance, simple counterexamples where the arguments don't hold.
> Hypercomputation isn't really a big part of the main thrust of complexity theory
I don't mean to imply that it was, though the results are actually relatively important elsewhere.
> That's not complexity theory, at least not the standard theory, which treats time and space (or circuit size) more abstractly than concrete physics.
More, but not totally abstractly. Steps and cells being vacuous primitives, they're not literally space-time, but within orthodoxy there's absolutely a partial morphism that's implied. That's why they're named like that. You are supposed to have them live close together in your head.
>There are, however, theoretical reversible models, just note that they don't yield different "classic" complexity classes
I know that some don't, but for example quantum models to use your own example, while not technically reversible in the absolute sense, do possess some reversibility capability and do derive different complexity classes.
I think it's very obvious that there should be reversible computational models which yield different complexity classes from the typical ones. To me for a field to qualify as a study on the nature of computation, it should probably be able to design one totally a posteriori, if in a higher order language. Complexity theory might be invoked in such a construction, but it's not the one doing the building. It's one of many in an orchestra.
Here's a question I have, since you do seem pretty well versed on CT. Universal quantification over complexity classes of first-order systems, used anywhere in the abstract?
> Universal quantification over complexity classes of first-order systems, used anywhere in the abstract?
I'm not sure what you mean by "complexity classes of first-order systems" and by "in the abstract".
But it seems like you're asking about the intersection of computational complexity and formal systems, and there's definitely work there. I already mentioned proof complexity, which analyses the number of deduction steps needed to prove something in various formalisms, and there are famous undergrad-level examples, such as TQBF (https://en.wikipedia.org/wiki/True_quantified_Boolean_formul...). But an intersection that is of more interest to me, as I'm interested in software correctness, is that of the model-checking problem.
Now, many people are confused whenever the model checking problem is discussed, because they confuse it with model checkers, which are a set of algorithms intended to solve the problem, but complexity theory is typically interested in the inherent difficulty of answering problems regardless of the algorithm used to do it. So the model checking problem is that of determining whether a formula in some formalism implies another formula, and its inherent complexity exists regardless of whether this question is answered via a formal proof or by some technique involving the logic's semantics. In the context of software verification, the model checking problem is that of determining - by whatever means - whether a program satisfies some non-trivial property.
Philippe Schnoebelen has some papers on the model checking problem in temporal logic (https://lsv.ens-paris-saclay.fr/Publis/PAPERS/PDF/Sch-aiml02..., https://lsv.ens-paris-saclay.fr/Publis/PAPERS/PDF/DLS-jcss-p...). One of his findings that I've found most interesting with regards to programming is that programming languages cannot, in general, make answering the question of whether a program satisfies some property any easier. This result is surprising. The reason is that without a programming language, we could describe a program as a huge state transition graph (this is called a Kripke structure). In that representation, it's been proven that verification is linear in the number of states, i.e. there is no general approach that is faster than brute-force. Now, the size relationship between a program written in a programming language and its Kripke structure is easily exponential or more, so if there were no algorithm that's better, in the worst case, than a brute force of the Kripke structure, then obviously verification is intractable in the size of the program. However, the number of Kripke structures of size N that have a succinct representation in some programming language is far smaller than the total number of Kripke structures of size N. So it could have been the case that analysing programs would have been easier than analysing their Kripke structure (while ignoring their representation in the language). But Schnoebelen proved that this is not the case.
He also proves that program decomposition (and verification of each component separately) cannot, in general, make verification any easier (i.e. the model checking problem isn't FPT in the number of program components).
These results are far more recent than the hopes expressed in the seventies and eighties that we'll be able to prove the correctness of all/most/many programs we write, and indeed, even though the results talk about the worst case, what we've seen in the last few decades is that the power of program verification indeed behaves more like the worst case than something far from it. The gap between the size of programs we can verify and the average size of programs we write has only widened (what saved the day has been the effectiveness of unsound methods, but that's a whole other discussion).
Isn't complexity theory usual based on a random-access model, not any kind of Turing machine?
MT Turing machines aren't really all that different. Or from pointer machines for that matter. They map nicely together.