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.
> 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.
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).
The parent is making a point about the rate/scale at which technology replaced workers. If you think the hypothetical is too extreme, then what would a more realistic version be? Are you uncertain about the rate of disruption?
Yeah, a corner case (streaming) and good developers working very hard.
The original SSE (SIMD) extensions were actually written with this use case in mind. When they first came out, the compilers were awful. They've since caught up.
>Few of my teachers really understood the things I wanted to learn, my peers weren't interested in the nerdy things I was, and my parents certainly didn't have the wealth to provide me with private tutoring.
I can understand saying that when you're in middle or high school. But as a 5 year old? This comment has to be a joke?
It wouldn't really surprise me if the average kindergarten teacher (or just adult) had no idea how e.g. an air conditioner or an elevator or one of those emergency flashlights that you can power by shaking or any number of other everyday things works.
Are you asking me to believe that the educational system underserves kindergartners because the average kindergarten teacher can't provide an education on your narrow technical interest?
The responsibilities of the average kindergarten teacher probably include 1) making sure your kids don't swallow glue, and 2) making sure little johnny doesn't throw another tantrum.
That's one interpretation: the system doesn't take of your specific needs and therefore it's neglectful or inadequate. Another interpretation is that the teacher is doing exactly what the school needs them to do because most 5 year olds aren't concerned with how air conditioners work. And perhaps it shouldn't be the responsibility of the kindergarten teacher to provide technical education?
There's a conversation to be had about the educational system underserving the intellectually curious. Trying to make that point in the context of kindergarten is a little absurd to me.
No one in this subthread said teachers aren't doing exactly what the schools need them to do; the OP you replied to said properly harnessed LLMs could be a boon for a smart, curious child. Why is that absurd for kindergartners? My oldest probably started asking me about everything she sees when she was 3. Curious, undeserved kindergartners exist.
The idea that they can be tailored to the needs and interests of every individual is the point.
I have a gripe with this attitude because it goes beyond browser use. Inserting the new fancy thing everywhere is often unnecessary and affects accessibility in a negative way for a nonneglible number of your users. And that was the point of the article, right?
Taking the conversation slightly outside the original context: if I go to a restaurant, should I have a phone and an app ready so that I can order food? If I go to the gym, should I have a gym app ready so that I can sign in? I don't like having to do that. But that's just another instance of this same attitude.
It’s very difficult for the average person to use a ten year old browser; in fact I’d offer that the only way to use a ten year old browser is to be an expert and do so intentionally.
There are plenty of people with old android phones with no free disk space using ancient browsers.
There are plenty of people still using windows 10 with updates turned off or wedged for whatever reason.
These people just use the sites that work. They aren't computer experts, and might not even realise why half the internet doesn't work - they just think that's the way things are.
I think you're conflating "old device" with "10 year old browser" here. E.g. for:
> There are plenty of people still using windows 10 with updates turned off or wedged for whatever reason.
It'd be "the pool of people who installed Windows 10 immediately in the launch year but somehow accidentally blocked their browser from updating in the 10 years since, weren't able to fix the issue as the web slowly stopped working, and are stuck using that computer anyways" not "the pool of people still on Windows 10".
The latter won't have many non-intentionally pushed into "10 year old browser status" until 2038 at the earliest.
When will Microsoft stop doing Windows 10 security updates?
I have a 10 year old laptop with 32GB of RAM, GTX 970 6GB and an SSD.
For many things it is better than any 16GB work issued laptop (that often come with integrated cards - so you wont be able to run any AI model on them). Although the old ssd is starting to show its age (perhaps a full system reinstall would solve this, other option is to get a new one).
The old laptop does not have UEFI so it could not get the (free for some time) Windows 10 to 11 upgrade.
I am smart enough to install Firefox on it and update it, but the official Windows 10 updates will stop coming soon.
I was effectively kicked out by Microsoft because my device is "old". Even if it is beefy enough to browse the internet and watch youtube.
Note that I bought a new beefy laptop now that I hope to use for the next 5+ years (hopefully more), but who knows if they wont come out with some new idea, like UEFI 2.0 for Windows 12 - that again will mean we need to buy new hardware and new windows.
On an unrelated note I want to turn the old laptop to a linux machine - for fun and learning, but dont have the time for that.
> When will Microsoft stop doing Windows 10 security updates?
Last October, unless you are on an LTS type version - in which case somewhere between 2028-2032 (depending on the exact version). Edge will still update until at least 2028 even though the OS stopped receiving updates... though I'm not sure I would wish either of those usage scenarios on someone :).
> The old laptop does not have UEFI so it could not get the (free for some time) Windows 10 to 11 upgrade.
The free registration, they never actually axed the program at the end date https://techcommunity.microsoft.com/discussions/windows10spa.... Just make sure you use the same edition (e.g. Pro -> Pro). You also don't have to do an in place upgrade to do it. In your specific scenario, you would have to bypass the install requirements in the installer to get around the lack of UEFI though.
Hope that helps, Windows 11 is definitely a bit of an annoying step (even once it's installed).
While I agree with your general gist and definitely your final paragraph,
> There are plenty of people with old android phones with no free disk space using ancient browsers.
How many people have 10 year old phones? I've got an 8 year old iPhone XR which I keep around as a backup/travel device because it's not worth selling, and the battery is… not happy even in airplane mode.
For me to have a 10 year old mobile browser, I'd have to have kept the iPhone SE 1 (or was it a 5c?) that I bought second hand in 2018, and not upgraded it since I bought it. I got rid of it because the battery wouldn't hold a charge for 10 minutes.
I have a 10 year old cell phone that still gets regular use. Works just fine for things like phone calls, texts, youtube (newpipe), termux, and note taking. Original battery isn't great at this point, but a new one is maybe $15. Zero reason to replace it.
I've a Xiaomi Mi 6 phone (2017 model) that I still use as a fridge-mounted shopping list and it's using the latest version of Chrome. I think it would be quite the stretch to find a user using a 10 year old browser.
It's fine to support such configurations by accident, but you shouldn't try to support them intentionally. You will end up dropping support eventually regardless but the skeletons will live on in your codebase as tech debt.
The needs of the many outweigh the needs of the few.
Eventually you are making things worse for your vast majority of users when you have to e.g. make them install a native app for a video call or use a TLS version that is broken to support those Gingerbread Android phones
or windows 8[.1], or windows 7, or windows xp... there's a lot of old hardware out there, not every is rich/tech savvy (see also: old people) enough to purchase a new device even 10 years later
I'm not sure this is a realistic use case to try and support. A 10 year old android phone likely has a battery life measured in 10s of minutes, and really isn't something we need to worry about.
I'm currently using >7 year old Android phone. The batteries on these things are child's play to replace (especially after you've done it the first time and removed the pointless adhesive in the battery compartment). I will consider upgrading once new devices return to feature parity with my current device (apparently never).
While I'm of course an edge case, the fact that Google, Apple and Samsung all provide >5 years OS support for devices now (and battery replacement services) suggests that many people hang onto their old phones for a long time.
That said, I'm not using 7 year old software on my phone. That would be insane. And my browser (fennec) was updated just a few days ago.
You get the guy at the mall to swap in a new battery for $50 in most parts of the world. Its cheaper to do that every few years than buy a new phone, and I have several family members who refuse to upgrade on principle, because modern phones grew too large for their hands/pockets
There’s also being poor, or working for an organization that’s poor. In both cases the obsolete(?) software might be various degrees of intentional, but the alternative is usually worse anyway.
I support a bevy of older people with older computers, senior-citizen types. Upgrades are expensive. Monetarily, but also in retraining. These folks don't want the latest UI, they want what is familiar, and retraining is super annoying.
Computers that were EOL a few years ago, running ten-year-old browsers, are absolutely routine.
That's a choice by the people who make websites and browsers that forces the average person to buy a new computer. If we all cared about letting people use old computers, this wouldn't be the case.
I doubt that for the hackernews audience that the age of the browsers is an issue. I would say in practice that 90% is nowhere near what is achieved - that it's closer to 90% and amongst the hackernews audience probably lucky if it gets to 50% because of our use of anti-tracking and ad blockers.
Respectfully, you may live in a bubble of fairly tech-savvy folks. Most of my extended family run 10+ year old laptops as their daily drivers. Their phones are often on the second or third battery replacement. They don't install updates very often (if at all). For the most part they are still more proficient with tech than many of their peers.
The same way people generally equate luddism with anything. By entirely misunderstanding what it was to make a point that sounds snappy without all of that boring understanding history stuff.
Look, I don't spend most of my time online criticizing AI progress. But what does your response even mean? People hallucinating work and solutions isn't commonplace at all, right? What industry do you work in where people hallucinate with frequency?
I can't speak to GP's intention, but I've personally witnessed a guy on my team who was trying to position himself as the go-to technical dude. He was jockeying for a management role. When QA or customer support had questions about our products, he'd always have an answer. I would say that at least 50% of the time, his answer was completely fabricated nonsense. He'd wildly misrepresent projects that his teammates were working on. I also saw several incidents of cargo-cult programming from him. Bizarrely, this never bit him in the ass and now he's a middle manager at a FAANG. This experience leaves me without much hope for the future of software development as a career.
I don't think your comment represents the situation very well. They allowed the user to upload the data and they're storing the data regardless, right?
That's fair push back. In defense, my comment was motivated by the OP's assertion (multiple times) that this is merely an example of corporate greed. I don't know what the original user-agreement was, but it seems to me that common sense would say that you have to make money some way. If this business at one point offered a free service and at some point market pressures showed them that wasn't going to work, so they needed to do something else to remain solvent. Egress is not free, so merely uploading and storing is not an argument for free retrieval.
I like this answer. For me it's not about showing others that you're correct. Instead, it's about feeling like you're being heard/acknowledged.
I'm not trying to be the "lone free thinker". But if I see a hivemind, I occasionally insert my opinion with the intention of having a different perspective be recognized.
It's important to feel heard, but an issue in an argument is that no one is being heard and you're yelling past each other. You don't feel heard by more strenuously arguing your point; you make a calm, genuine effort to hear them, and then hopefully they'll reciprocate the favor. At the very least, you break out of the doom loop and walk away.
What is an example of a model of computation where complexity theory doesn't apply?