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

▲

ragall 2 hours ago | parent | next [-]

> 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 42 minutes ago \| parent \| next [-]
		> 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 25 minutes ago \| parent \| prev [-]
		> 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.

▲

ux266478 2 hours ago | parent | prev | next [-]

> 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 2 hours ago | parent [-]

>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 an hour ago | parent [-]

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.

▲

pron 36 minutes ago | parent | next [-]

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

▲

inigyou an hour ago | parent | prev [-]

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

	▲	ux266478 18 minutes ago \| parent [-]
		MT Turing machines aren't really all that different. Or from pointer machines for that matter.

▲

aaron695 2 hours ago | parent | prev [-]

[dead]