And the result that it's now false apparently doesn't imply NP!=EXPTIME either since it seems not strongly subexponential enough to offset the expansion in variables from reductions. See the other comments for a much better explanation.]

Showing 3SAT (technically #3SAT) can be solved in less than EXPTIME resolves this. It's only slightly subexponential, not even quasipolynomial, but it is a very surprising result. And that too a constructive algorithm.

Edit: Apparently not true, the constructive algorithm given may not survive under reductions. See discussion in https://news.ycombinator.com/item?id=50252769

>We give a deterministic algorithm for exactly counting the satisfying assignments of an arbitrary k-CNF formula [in superpolynomial but subexponential time]

No LLM can help companies that didn't care about software quality in the first place. If they did, they wouldn't have fired QA testers. And now that they've been gone for a decade while revenues have soared, why would they bother using LLMs for QA testing when they could execute on the stakeholder's vision instead!

You'd expect to see the majority of benefit to independent devs who previously _couldn't afford_ QA or a full team, and now can. But since the target audience for this stuff is niche, you're less likely to hear about it unless you're plugged into the subcommunities (see e.g. how LLMs have helped with game preservation, retrogaming).

But most real-world programs are maybe not that "expressive" since we don't even want them to be capable of infinite loops (since those would often be denial of service vectors). So you should usually be able to prove that they halt (and presumably other properties as well), especially when you allow agents to rewrite things to pull out invariants that make proofs easier (as they did).

And for cases where getting clean invariants are difficult, I imagine you can just hack it by having some cutoff which trivially ensures things always halt. (Not sure what the equivalent would be for "no bug" proofs, probably rejecting things that are technically valid input per spec but seem unusual?)

* Start with the usual FFT convolution for polynomials, viewing integers as a polynomial in a given base evaluated at a certain point

* In undergrad you (hopefully) saw polynomial multiplication can be done in nlogn via convolution using FFT, but that assumes complex integer addition/multiplication is O(1). Here we need O(log x) bits to simply represent a number x on a real machine.

* If you use naive (n^2) multiplication for those butterfies, then you end up with O(n[(log n)^2]).

* If you recursively use FFT for the digit multiplication at those butterflies, then you get something like O(n[(log n)^(log log n)]).

* Schonhage-Strassen realized that instead of doing FFT in C where the butterfly involves multiplying by \omega (\omega being roots of unity), you can work in a different ring where 2 is a root of unity and so it's a cheap bitshift, but were constrained in how finely they could break subproblems (could only break an n-bit integer into sqrt-n subpproblems each of sqrt-n bits), resulting in an overall O(nlogn * loglogn).

* The 2019 O(nlogn) version (supposedly, this is out of my depth) found a way to use some technique of "Gaussian Resampling" to do the matrix convolution via _multidimensional FFT_ in a ring where multiplying by root of unity became cheap _and_ subproblems could be finer. The bottleneck was thus only the addition/subtraction in the O(log n) butterfly layers, each of which does O(n) work for total of O(n logn)

* OpenAI's paper uses a fact that it's apparently easier to compute multiple butterfly layers "simultaneously" than doing them one at a time independently (page 10). There is some sort of implicit reuse because the later layers mix the outputs of earlier layers, and they take advantage of this to avoid having to write out layer 1 outputs separately from layer 2 outputs, and instead work in some coordinate system where they can intermingle them. This apparently amortizes to some tiny fractional epsilon shaved off of a layer, and since the whole FFT is recursive they can apparently save a factor of (1 - epislon)^(log log n) overall across "log log n" recursion depth, which is apparently where that ridiculously small overall exponent comes from.

>neurons generalize, work together, and build abstractions over layers. Somewhere along the way we overcomplicated that picture, but looking harder brought it back.

and it does seem that if what the article claims is true, then it really is that simple. To clssify e.g. fruit they first detect curves/shape, then the neurons downstream of say the "circle" detector may distinguish based on color, then the ones downstream of a specific color distinguish by texture, and so on. By the end, what you have are neurons that activate only on very specific combination of features, which map to each fruit.

In both cases what they really are is an abstract concept defined by things that satisfy some definitions, but in practice it's easier to just look at a few concrete examples like Maybe.

This only works of course if the game is actually fair, and you have infinite money reserves.

And then unlike the usual monotone queue for sliding max/min, this works for any monoid since you're never comparing two elements.

To some minor extent this is normal, https://en.wikipedia.org/wiki/Nasal_cycle . Or at least the alternation itself is probably not the issue.

I don't have any specific experience in ML but I always liked the formalism presented in https://www.youtube.com/watch?v=J1YCdVogd14 as a way to unify everything

I thought with NoPE schemes you don't even need it during pretraining

https://arxiv.org/abs/2305.19466

https://sebastianraschka.com/llm-architecture-gallery/nope/

Given the causal mask and the way attention works LLMs can implicitly propagate a signal for ordering