5 ms·

Corollary: P does not mean easy. 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 tha

• dwattttt 3y ago
  A terrific teardown of tracking down an unexpected O(n^2): https://randomascii.wordpress.com/2021/02/16/arranging-invisible-icons-in-quadratic-time/ https://randomascii.wordpress.com/2021/02/16/arranging-invis...
  • gdprrrr 3y ago
    Also reminds me of the GTA online case. https://news.ycombinator.com/item?id=26296339 https://news.ycombinator.com/item?id=26296339
  • chriswarbo 3y ago
    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 https://accidentallyquadratic.tumblr.com
    • loupol 3y ago
      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/accidentally_quadratic/glbeiob/ https://old.reddit.com/r/programming/comments/jdylxs/acciden...
• fooker 3y ago
  Interestingly being P complete has another unexpected 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.
  • s1dev 3y ago
    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)
    • fooker 3y ago
      Yes, linear(-ish) dependency chains so that your threads have to wait for one thread to provide a result (infinitely often).
      • gnull 3y ago
        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"?
        • fooker 3y ago
          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.
          • gnull 3y ago
            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.
    • Cerium 3y ago
• tetha 3y ago
  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.
  • adalacelove 3y ago
    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.
    • shenberg 3y ago
      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.
      • adgjlsfhk1 3y ago
        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.
  • globular-toast 3y ago
    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.
  • 3y ago
• nabla9 3y ago
  Matrix multiplication is O(n^2.73) time and O(n^2) space. That's what eats bigger and bigger chunk of electricity nowadays.
  • eternityforest 3y ago
    Are there approximations? I assume it's for machine learning right?
    • touisteur 3y ago
      There's multiplication by hashing, which is a very fun subject, look it up :-)
    • nonameiguess 3y ago
      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.
  • 3pac 3y ago
    Where does 2.73 come from?
    • 3y ago
• deleted 3y ago
  [deleted]