A terrific teardown of tracking down an unexpected O(n^2): https://randomascii.wordpress.com/2021/02/16/arranging-invis...

Also reminds me of the GTA online case.

https://news.ycombinator.com/item?id=26296339

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

Last post was made in 2019. (If you click on the name of the post it shows the timestamp at the bottom)

Blog author stated on Reddit in 2021 that he wasn't maintaining it anymore[0].

[0] https://old.reddit.com/r/programming/comments/jdylxs/acciden...

Interestingly being P complete has another interesting consequence: it means your problem is going to be difficult to parallelize.

This is why parallel SAT solvers are barely faster than the usual ones.

SAT is NP complete, but a crucial step in SAT solving (unit propagation) is P complete.

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)

Yes, linear(-ish) dependency chains so that your threads have to wait for one thread to provide a result (infinitely often).

Are you stretching "this specific strategy for parallelizing P that I came up with won't work" to "there's no way to parallelize P"?

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.

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.

Cerium is correct, we don't know if P is efficiently parallelizable.

Is there a formal proof of what you're talking about that we can read?

Are you perhaps confusing P with P complete?

https://www.researchgate.net/profile/Walter-Ruzzo/publicatio...

How does that matter? P-Complete is a subset of P.

What am I looking for in this 300 page document? Proof by intimidation, eh?

There is an easy daily example: the PBKDF function, the whole point of which is to be expensive to compute, and impossible to efficiently parallelize.

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.

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

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

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.

Matrix multiplication is O(n^2.73) time and O(n^2) space. That's what eats bigger and bigger chunk of electricity nowadays.

Are there approximations? I assume it's for machine learning right?

There's multiplication by hashing, which is a very fun subject, look it up :-)

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.

Where does 2.73 come from?

Naive method is O(n^3).

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.