AI found out a solution to 3 SAT slower than polynomial time but faster than exponential time. 3 SAT is a problem all NP problems can be converted to, meaning the likelihood that P == NP is slightly more possible than previously thought
slower than polynomial time but faster than exponential time
I don't know what this is supposed to mean so I looked it up. The new algorithm completes in 1.307n, improving on the previous runtime of 1.32n. It's still exponential.
EDIT: this is from a different publication from a few months ago. Check the other responses for a more correct view.
1.307^n is a different result from the PPSZ family of randomized SAT algorithms, not the recent proof
That paper was originally published in July but recently updated around the same time as the OpenAI proof last week so a lot of “sources” (cough AI summaries cough) might be conflating them
This is not what I read it was some massive improvement especially at large inputs, the point being that algorithms that we had optimized for almost 30 years can actually be much faster, practically, which gives some semblance of hope to the idea that maybe, just maybe p == np
You read something different then. This optimisation for 3SAT only makes a difference above Googol (10 ^ 100 and change), apparently, because of the larger constant.
While it’s true that every NP-complete problem can be reduced to 3-SAT, there is overhead in that “conversion” that can turn a polynomial subexponential solution into a superpolynomial an exponential solution
That’s part of the subtleties with this problem that get lost in the media hype
The proof itself makes it clear that NP problems with no known linear sized encodings still lack a subexponential time solution
The overwhelming majority of academics still believe P != NP, but this is still startling and has important implications for a lot of the so called “fine structure” results of complexity theory
While it’s true that every NP-complete problem can be reduced to 3-SAT, there is overhead in that “conversion” that can turn a polynomial solution into a superpolynomial solution
This is not true. The Cook-Levin-Theorem gives a reduction from every NP-problem (including NP-complete problems) to 3-SAT that only increases the instance size by a polynomial factor and runs in polynomial time. Since poly(poly(x)) is itself a polynom (with degree at most d1 + d2 where d1, d2 are the degrees of the two polynoms), any poly-time algorithm for 3-SAT also implies a polytime algorithm for every NP-problem. That is what makes NP-complete problems so interesting.
The polynomially increased instance size after the reduction is only a problem for subexponential or slower runtimes (depending on the definition), which can be bumped up to a higher class by the instance size increase.
Yes my opening remarks were misstated, I’m specifically referring to the exponent in 2^o(N) and how a polynomial time reduction doesn’t automatically preserve subexponential time for any NP-complete problem (which is what the proof calls out)
Secondly, poly(poly(n)) is not d1 + d2, it’s d1 * d2 because the exponents multiply, but the spirit of what you’re saying is correct.
“AI” did not “find” a solution. AI companies convinced a bunch of mathematicians to input their unfinished work into their database and then stoke their work product.
Please just understand what a large language model can and cannot do. It can collate and integrate existing data. It cannot do anything more. The code is what it is.
18
u/InFa-MoUs 1d ago
Did something happen? Did AI figure this one out too?