Most things that you do on the computer, you want to be O(n) or less; maybe O(n log n) or even O(n log^x n), but no slower than that. That means if you get a bigger problem, you can generally just get a proportionally bigger computer and be all set.
Now, sure, there are plenty of O(n^2) problems where the n stays small enough, or you don't mind waiting or spending a ton of money on it. But just because something is in P doesn't mean that you want to be solving it with a polynomial time algorithm on a regular basis.
Our CS-Prof also had another interesting point: P = NP could be true without changing many things in reality.
This could occur if the reduction of an NP-complete problem onto a polynomial problem results in a runtime of such monstrous polynomial degree that the exponential algorithms are just faster for every tractable problem size. Something like this exists in some graph algorithms - theoretically faster algorithms exist, but in practice, they are a lot slower than the theoretically slower algorithm until completely silly graph sizes.
This could turn even more frustrating if the proof was nonconstructive.
Another interesting take: P != NP could be true, while changing MANY things in reality.
Basically all modern asymmetric cryptography in common use rely on the difficulty of either integer factoring or discrete logarithms (including discrete logarithms of elliptic curves). The problem is, none of those problems are proven to be NP-complete! Even if we proved P != NP, there could still be polynomial time algorithms for integer factoring and/or discrete logarithms.
Staying in the realm of polynomial complexity matrix multiplication comes to mind, where we are approaching more and more O(n^2), where O(n^3) is the naive, but more common implementation.
In terms of practical algorithms, the Strassen algorithm (O(n^2.8)) is the only one that has runtime advantages for matrix sizes that aren't enormous, and even then, it's not always used because it has two non-trivial costs: reduced numerical stability and more memory space requirements for intermediate results.
It actually doesn't require more memory for intermediate results (see the Strassen reloaded paper). It's more just that it's a ton of work to implement well (even compared to a regular gemm which is already hard), and the benefits only start showing up at pretty large (~4000x4000) matrices.
> This could occur if the reduction of an NP-complete problem onto a polynomial problem results in a runtime of such monstrous polynomial degree that the exponential algorithms are just faster for every tractable problem size.
You don't even need to go that far.
n^8 is smaller than 2^n once you get past 44, still well in the tractable range, but encrypting something against n^8 brute force is a pretty reasonable task.
This is similar to Knuth's reasoning for P=NP. Essentially there might be algorithms for these problems that are simply so complex that we might never know them.
The "accidentally quadratic" blog collected such things. Not sure if it's still being updated since Tumblr's mass exodus (the posts don't seem to show timestamps) https://accidentallyquadratic.tumblr.com
Is there some good intuition why P-complete problems are difficult to parallelize? This is the first I've heard of it (but then again, I'm usually interested in more obscure complexity classes)
This is the first I have heard of it as well (and I have properly studied NP complete in graph theory, so I don't know why this missed my attention). It seems that P-complete are difficult to parallelize by definition as they are the set of tractable problems (as opposed to NP) which don't parallelize well.
"The class P, typically taken to consist of all the "tractable" problems for a sequential computer, contains the class NC, which consists of those problems which can be efficiently solved on a parallel computer. This is because parallel computers can be simulated on a sequential machine. It is not known whether NC = P. In other words, it is not known whether there are any tractable problems that are inherently sequential. " From: https://en.m.wikipedia.org/wiki/P-complete
It's not by definition, there's a bit of math behind it! :)
The intuition is that the hardest problems in P have linear dependency chains.
If you could have a good parallel algorithm for a P complete problem, you could take a problem with a dependency chain and solve parts of it in parallel without waiting for the results those parts are depending on.
It’s more like : you win a Turing award by finding a strategy to parallelize this problem as you’ll be able to use that approach to parallelize all problems in P, proving NC = P.
This applies both ways. You'll win a Turing award if you prove NC ≠ P, which is kind of what you said — at least, that the best way I see of reading your first and a few following messages.
Not in the sense you mean. I think the other comment is talking about multiplication without carry, which is a simple form of hashing, but no one I'm aware of uses this for numerical computations. However, floating-point multiplication is inherently an approximation, and the precision of the input is first limited to the bit depth of the sensor channel no matter what, and then typically reduced further anyway by norming everything to fit between -1 and 1 in order not to overweight the importance of input features with naturally larger values as well as to just fit into f16 registers that a typical GPU might have tens of thousands of. Plus, while I don't know what they're doing these days with vector embedding in LLMs, with older school NLP, the probabilities you're dealing with are so small that the only way to reliably get joint distributions is to take the log and add instead of multiply. Otherwise, you'd be very quickly rounding to 0 in what can fit into any floating-point width.
Something to keep in mind is a lot of these matrices are sparse, though. When most of the entries are 0, specialized data structures that know this can avoid doing all of the pointless multiplication by 0 operations. This saves far more time than some kind of approximate multiplication would.
Strassen algorithm drops it to O(n^log2(7)) = 2.8074 because it divides the process into 2x2 matrix multiplications that can be multiplied by 7 ops instead of 8. Strassen is practical algorithm.
You can still optimize and get to 2.371552 with complex trickery, but these are galactic algorithms, meaning that matrices are so big that you can't even construct them on Earth.
I think it's funny that the majority of causes you list (isolation, not enough physical activity, little vitamin D/Sun exposure) wouldn't apply at all to the group you cite as having widespread issues (girls HS volleyball team).
As someone who struggles with mental health issues, and frequently not getting enough of many of those things mentioned, I've worked to try to do better about some of that; and it can sometimes help a bit. But the whole "get more exercise, touch grass, see a friend" isn't the magic cure-all that some people make it out to be; and worrying about doing enough of it can become a stressor all on its own. Additionally, seeing them as the solution can sometimes lead to harmful obsessive behaviors of trying too hard to seek them out, at the expense of other things like work or family time.
Anyhow, not saying that getting more of these things is bad, or that they have no effect. Just that a lot of times discussions of mental health online feel very reductive. More exercise, more outdoor time, more time with friends, more antidepressants; each of these could potentially have positive effects, but they can also have negative effects, or be unobtainable, or there could be one of myriad other issues that need to be addressed, or there could be situations, either mental, physical, or social that are so broken that they can never really be addressed, just lived with or in some cases not even that.
I think for people under 30, reducing social media exposure would help a lot (in general, for all ages - but many of those under 30 seem to live and breathe social media esp. girls/women)
And even when it doesn't block you completely, it delays website loading, makes you jump through frustrating captchas, etc.
It's probably third in the list of frustrating web behaviors in the past couple of years (behind GDPR popups and registration/paywalls that seem to have gotten much worse recently).
And somehow there are some sites that I get CF delay walls on every time I visit.
This feature is utterly broken for a good web experience; it pushes users away from sites which use it.
Every time that "checking your browser" page comes up for a legitimate user should be considered a failure. Sure, it can maybe happen a few times in a thousand, but the feature is utterly broken if it comes up every time I visit the same site from the same browser not in private mode.
It's worth noting that the websites that you are visiting chose Cloudflare, and have enabled the features that irritate you. They have browser integrity enabled, have bot protection enabled, maybe turned the security level up (gitlab famously is a nuisance because they lean heavily on Cloudflare for protection). Sometimes they've wholly barred VPNs or entire geographic areas! And that is entirely the decision of website operators, and note that they did all of this before Cloudflare came along.
Cloudflare's customers are website operators, not you the end user. Those website operators seem pretty pleased with the service, so clearly they are doing a good job for the people who they are building it for.
Agreed. The same goes for the 3rd party "data privacy" popups which simply hide a long list of opt-outs several layers deep in a Vendors list. I refuse to use such sites and I let them know by email.
In what way is it an attack? (I know what a mitm is, I'm not asking you to explain that - I'm pretty conversant in the concept of a proxy, I'm asking you to explain why it's an attack specifically)
I don't get it. They offer a service that that people choose to sign up for and take active steps to use. I don't see how that's an attack. Honestly I'm still trying to understand who is being attacked.
Like is it an attack on the site owner - are you saying cloudflare is extorting them or something? That seems unlikely but I agree that would be a form of attack... it also doesn't seem to be what you're saying.
Is it an attack on the user of the website because the website owner successfully denies visitors it does not want? Does that mean that login credentials are a form of attack too? Would an on-prem load balancer or WAF that dropped all traffic from a region or matching patterns still be an attack?
The cloudflare customers who benefit from the bot protection do not see it as an attack. On the contrary, they see it as a defense from an attack.
Also, it’s quite disingenuous to label cloudflare as only slowing things down. One of their primary functions is a global CDN/cache which significantly speeds up otherwise bandwidth constrained sites.
Man in the middle attack typically implies an unwanted third party, which in this case is not true since Cloudfare is explicitly and voluntarily trusted by the host server. It wouldn't be all that different if the web server had the browserintegrity checks developed themselves.
This is precisely what Cloudflare is doing to end users - causing problems like OP (and myriad others) experience by slowing down and/or blocking major chunks of the internet
I understand that it may be viewed as unpleasant, but ultimately if you install a proxy on your end that the server does not like (say an ad-blocker), I don't think it would be fair for the server to say its suffering a MITM attack. Likewise, even if the client is not happy with the third party the server is requesting, it still doesn't make sense to call it a MITM, IMO.
And this is precisely why I don't bother reporting Cloudflare's failures to site operators anymore. I used to do it, when it was pretty infrequent. Site operators were usually concerned that something was blocking customers, but most were clueless about what was causing it or how to fix it.
Eventually I gave up. I don't even bother with their captchas or other stupid human tricks anymore. Whenever Cloudflare gets between me and the site I'm trying to use, I move on and shop somewhere else. Life's too short for this.
Why not take a screenshot of the CF error and send it to the website owner? It would freak me out if I thought a significant number of my website's users were being blocked by CF.
+1 to anybody who creates a site to name and shame CF customers who block legitimate traffic. For a few months now I've been taking screenshots every time this happens, but with no end goal. Complaining to the individual site owners feels like a lifetime commitment, and there are virtually none I need that badly.
I have done that numerous times. Even sent a screen recording of the Cloudflare spinner of hell. The response is always the same: you must be running some shady software on your machine.
Cloudflare is acting as judge and executioner, and site owners never accept that the product may be faulty.
How do you send them that when you can't access the contact form and/or contact information on their site because Cloudflare blocks it? (assuming a normal visitor, not someone who knows about whois etc.)
Grope has the same meaning in American English, and used in that context could be fine ("grope around").
But I have never heard "groper" used for anything other than some engaging in sexual assault. The benign sense of "grope around" isn't a sufficient part of an identity to ever use the word "groper", while he sexual assault sense is, so "groper" implies the sexual assault meaning.
It's entirely likely that the original author of this phrasing was thinking about it in the benign sense, but didn't realize that the phrasing would make many readers interpret it in the sexual assault sense.
It's extremely common for programmers especially to add -er endings to common verbs to describe functions or objects that do that thing. Even if you want to exclude the playful neologisms that use this -er ending (Googler, Redditer) you have only to dig into the archives of classic code to find plenty of examples of this and it usually means "one who X's", in this case, "one who gropes". The scrupulosity brigade being on high alert for any ambiguity notwithstanding.
I don't think I've heard 'groper' to describe the actor when it's a human assailant either though?
And 'dig' is a tool that searches (or 'digs') for certain information - one (and only one) of the meanings fits!
I'm not really interested in an argument about it, and I'm certainly not holding anything against or taking Evans to task over it, as I said initially it just seems like a misunderstanding or that the commenters were rude about it to me.
I thought TFA was otherwise excellent and I've enjoyed (& learnt from) her writing on many occasions.
There may be more hardware out there with SH4 processors, like some NAS boxes, but are they using or contributing to Debian? And when I look at a list of hardware with SuperH processors, half of the links are broken links: https://elinux.org/Processors#SuperH
SuperH seems like a niche architecture mostly supported by a single vendor and available in a few devices mostly in the Japanese market, without a huge amount of use in the Debian community.
RISC-V may not yet have as much extant hardware available, but there's tons of active development, and the open licensing model means that a lot of companies are working on RISC-V chips, which will then flow into hardware.
I'm not suggesting that SuperH would become an official port today when it is clearly dead. But the question is why it was never an official port even when it was in its prime. As for the installed base, it is absolutely terrifyingly large. They had a lot of wins in automotive, and popular consumer products like Sonos are based on it, or were for the first decade of that product line, and those products also run Linux.
Even in its prime, it simply didn't have enough interest from Debian developers for maintaining an official port.
With each release there are roll-call emails to help judge whether a port has sufficient maintenance to be included in the official release, and I generally see a single developer for SuperH/SH4: https://lists.debian.org/debian-devel/2013/10/msg00134.html
Debian doesn't sit down and do market research on amount of hardware shipped, and then allocate developers and resources based on that; they base whether there's an official port on whether there are already enough developers and infrastructure to maintain it, as builds failing on that port can block work on packages.
I am one of these DDs and also official kernel maintainer of the SuperH port. I am not responding to such roll-call messages because there is no new SuperH hardware on the horizon at the moment except for the stalled J-Core project.
Well, the current RISC-V buildds also take days to build GCC. On the other hand, the 64-bit SPARC machines have been among the fastest in Debian, yet there is no official port.
> So the answer to "why wasn't SH4 an official port" is likely "there simply weren't enough developers and infrastructure for supporting it."
I would argue that the main reason is that Renesas simply abandoned the architecture and replaced it in their own applications with ARM.
The prospective 64-bit SuperH port was dropped as well.
Yeah, I was responding to the "why wasn't it ever official even when it was reasonably popular", not why it's not now. Those threads I linked to were from 10 years ago or more.
I tried looking for any direct discussion in the past of making it an official architecture, and didn't find it, but I did find that it seems to have been slightly lower activity, and with some hurdles, and that there didn't seem to be much of a push to make it an official Debian architecture, while there's been active effort to make RISC-V an official architecture, that's been going on for several years.
Anyhow, I'm not a DD or DM, I've made a few contributions via maintainers, so you're clearly more involved than I am. I was just trying to shed some light on the question of why SuperH never was official, and as far as I can tell it's because no one ever put enough effort in to make it official, while they have done so for RISC-V. But maybe I missed some drama somewhere.
> I'm not suggesting that SuperH would become an official port today when it is clearly dead. But the question is why it was never an official port even when it was in its prime.
Because Renesas dropped the architecture and stopped paying developers maintaining it upstream.
> As for the installed base, it is absolutely terrifyingly large. They had a lot of wins in automotive, and popular consumer products like Sonos are based on it, or were for the first decade of that product line, and those products also run Linux.
That's true. But these systems were developed before Renesas stopped supporting the architecture.
My favorite "accidentally load bearing" artifact that I've found was a misconfigured sudo that would easily allow arbitrary code execution as root (it allowed passwordless sudo for a find command, which could be used with -exec), which a number of important support scripts for the product had been written to use. Load bearing privilege escalation!
I have had one issue related to systemd; at one point when doing a routine update there was some dangling symlink issue that caused systemd to crash. This wasn't catastrophic; a lot of things didn't work, but I was able to cleanly save and exit out of applications, manually run a sync to make sure everything was flushed to disk, and then hard reboot.
systemd hasn't been without issue, but I've definitely had fewer issues with systemd than I did dealing with broken init scripts or upstart prior to moving to systemd.
Generally, the displaced threshold is not because of the load of touching down, but because of clearance of obstacles. When landing, where you are aiming to land, and a standard glideslope, puts you over obstacles at a certain height. In some cases if you landed on the very end of he the runway, that would cause you to collide with (or have too low a margin of safety) over obstacles before the runway. The displaced threshold moves the glideslope further forward, allowing for better clearance over obstacles.
When it is impractical to locate a threshold at the beginning of the runway, it may be
necessary to apply a displaced threshold. A displaced threshold reduces runway length
available for landings in one direction. The portion of the runway prior to the displaced
threshold typically remains available for takeoffs. Depending on the circumstances
surrounding the displacement, operations from the opposite runway end may or may not
be affected. Refer to Appendix H for related information on declared distances.
Generally, a runway threshold displacement provides:
1. A means for obtaining additional RSA prior to the threshold.
2. A means for obtaining additional ROFA prior to the threshold.
3. A means for locating the RPZ to mitigate incompatible land uses.
4. A means for obstacle clearance prior to the threshold.
5. Increased arrival capacity with certain parallel runway approach procedures. See
FAA Order 7110.308, Simultaneous Dependent Approaches to Closely Spaced
Parallel Runways
Glossary:
RSA: Runway Safety Area
ROFA: Runway Object Free Area
RPZ: Runway Protection Zone
Note that all of the given reasons are for clearance of obstacles or various other mandatory safety areas based on clearance from taxiways or other runway traffic, not for durability of the runway.
