Beloved family cat died this morning for no good reason except that he was old. I'm wrecked and stuffing myself with edibles

Show Post

The formalism allows for a ton more. Does it allow for impractical algorithms? Sure. But over and over we've seen that getting to polynomial can be hard but then it can be optimized down from galactic. Polytime is a seemingly invariant property over machine models and that itself is bizarre/cool

Show Post

I disagree with the premise that this is abuse of the formalism

Show Post

we now know that 3-SAT can be solved without searching all possible options. That's pretty big imo it's still essentially exponential but we learnt something big and new about the problem

Show Post

I'm not an OAI fanboy by any stretch but I get confused at these cynical takes "oh the algorithm is not a speed-up for realistic inputs" It's true, of course, but it seems bizarre to me to pretend we didn't learn sth profound about 3-SAT, that there are cases where we don't need to check all inputs

Show Post