See also: Announcing three new discoveries in mathematics, computer science, and physics - https://news.ycombinator.com/item?id=50251344
While this has no immediate bearing on P-vs-NP, it is interesting to note:
- Early CS researchers like Donald Knuth entered CS in the days when regularly someone would come up with a surprising faster algorithm for some problem, and their intuitions were that most problems had faster algorithms than you'd expect.
- Later generations of CS researchers, as all the easy algorithms were discovered, and post Karp's definition of NP-completeness (and the Garey & Johnson book, say), began to specialize in proving hardness, and complexity theory with a “zoo” of complexity classes became more about separation and lower bounds, e.g. I've seen algorithms like Arora's PTAS for Euclidean TSP being described as a “failed attempt to prove a lower bound”. So an entire generation of researchers' intuition was mostly in the direction of an elegant universe with neat separation results (even if we couldn't get them).
- So e.g. surveys of computer scientists showed most of them believing that P≠NP, and someone like Knuth has always seemed a bit of an outlier for saying that maybe P=NP: his argument was simply that there are so many possible polynomial-time algorithms that we haven't explored, and maybe one of them with a large exponent could solve NP-complete problems. (In response to arguments that many researchers have failed to find any such algorithms, he would say that many researchers have failed to prove that P≠NP.) E.g. in 2017 when Scott Aaronson wrote his survey (https://www.scottaaronson.com/papers/pnp.pdf = https://www.scottaaronson.com/papers/pnp-kindle.pdf) he wrote:
> Admittedly, it can be hard to tell whether declarations that P = NP are meant seriously, or are merely attempts to be contrarian. However, we can surely agree with Knuth and Lipton that we’re far from understanding the limits of efficient computation, and that there are further surprises in store.
- What we've seen in this month is surprising unexpected algorithms, like o(n log n) algorithms for FFT and integer multiplication, and now this sub–exponential-time algorithm for 3-SAT. (Yes the ETH has had less support than P≠NP but I still gather it's unexpected.)
So (though I don't expect intuitions on P≠NP to change, and probably that's still the right intuition… but I'm just an interested amateur), maybe there will be a bit of a swing of the pendulum back to the idea that maybe clever algorithms exist that we just haven't thought of.
This is an amazing and unexpected result. To be clear though, it does not imply that NP is subexponential: "Note that runtime bounds of the form 2^o(n) do not transfer under general polynomial-time reductions (2^n^o(1) would be needed for this), so our result does not imply that general NP problems admit subexponential time algorithms."
Edit: To explain more, it is guaranteed that you can reduce any NP problem to 3SAT in polynomial time with a polynomial factor in input size. You still have to solve it.
If 3SAT were solvable in polynomial time, then polynomial(polynomial(x)) = polynomial(x) and you're implied to have an overall polynomial time solution.
But what we have here is that 3SAT is solveable in subexponential time. subexponential(polynomial(x)) is not guaranteed to be sub-exponential.
Further edit: The subexponential solution does carry over to any (?) problems that have can be reduced to 3SAT in a linear number of variables. They list: Counting independent sets, Counting proper q-colorings, Counting perfect matchings.
> The subexponential solution does carry over to any (?) problems that have can be reduced to 3SAT in a linear number of variables. They list: Counting independent sets, Counting proper q-colorings, Counting perfect matchings.
Wouldn't that also include functions that can be evaluated in hardware using a fixed number of gates? E.g., symmetric cryptography?
> To be clear though, it does not imply that NP is subexponential
Is there a subset of NP problems for which a subexponential algorithm would witness the entire NP class being subexponential?
Yeah, that's NP-complete problems.
It's NP-complete problems if "subexponential" means O(2^{n^{\epsilon}}) for every \epsilon>0.
If subexponential just means 2^{o(n)}, (as it is here, O(2^{n/\sqrt{\log n}})), then no. E.g. if the cost of the reduction took you from n to \sqrt{\log n}n, then you'd be back to exponential time. The Subexponential Reduction Family is the class of problems that preserve subexponential time in the second sense.
That is unfortunately not the case
Can you explain more?
After some back and forth with AI, I think I understand: 1. The Exponential Time Hypothesis being false shows that 3SAT specifically is sub-exponential time 2. Any NP complete problem can be changed into 3SAT in polynomial time
Put these two together and you would think that they would mean that any NP complete problem can be solved in sub-exponential time. But this isn't necessarily true because changing the NP complete problem into 3SAT can increase the number of variables, which can theoretically negate the sub-exponential time.
"Any NP complete problem can be changed into 3SAT in polynomial time" - if I remember correctly, turning an NP-complete problem into 3SAT is not part of the problem statement - it just means that when working with NP-complete problems, they are always translated to 3SAT first, and whenever someone is trying to prove something they are working against 3SAT.
Oh ok, I understand what you mean.
(By the way, I think you mean NP-complete, not NP-hard. The Halting Problem is NP-hard.)
Thanks for the correction! I updated my answer to fix that :)
oh that actually helps a lot. I was tying myself in knots trying to think it through.
P=NP -> 3SAT has a polynomial time algorithm
P=/=NP -> 3SAT has no polynomial-time algorithm
ETH is true -> 3SAT has no subexponential time algorithm
ETH is false -> 3SAT has a subexponential time algorithm
------
ETH true -> P=/=NP
ETH false (!!!) -> P ?= NP remain unsolved
No I get that, but I don't get how proving 3SAT can be proved in subexponential time does not imply all NP-complete problems can be as well, since they can all be reduced to 3SAT in polynomial time.
(2^sqrt(n))^2 = 2^sqrt(n) * 2^sqrt(n) = 2^(sqrt(n) + sqrt(n)) = 2^(2 sqrt(n))
but
2^(sqrt(n)^2) = 2^n
...that's...not how exponents work
That last statement is not correct. (2^sqrt(n))^2 equals 2^(2 * sqrt(n)). If you just take n=1 in your expression you can see the error, your (2^sqrt(n))^2 yields 4, while 2^n is just 2.
Gotcha, thanks
[dead]
To achieve this you would need to show that 3SAT is solvable in 2^{n^c} time for every c>0, not just a single c<1.
In this case they have c = 1-0.5(\log \log n)/(\log n) which is approaching 1 for large n.
Misunderstood your question sorry, I have no idea!
The algorithm's runtime is in faster growing than O(exp(n^a)) for any a < 1. It's not subexponential in the sense that factoring is, which I believe has a secondary exponent of 1/3 under the best algorithms.
It's still a big result, but it's mostly theoretical. It might help explain, structurally, why most SAT instances are far easier than an exponential model would indicate.
For example, a 2^√n subexponential algorithm then used on an input after a n^2 polynomial reduction from some other NP-complete language incurs a total running time of 2^√(n^2) = 2^n, which again is exponential.
Yep! Or for a slightly generalised example, if we pick our sublinear function of n to be n^(1-epsilon) for some small epsilon > 0
then 2^(n^(1-epsilon)) belongs to 2^o(n)
Suppose p(n) is some polyonomial in n, our polynomial reduction. Let's make it a monomial for simplicity, p(n) = n^a
Does 2^(p(n)^(1-epsilon)) necessary belong to 2^o(n)?
No, that only holds if (n^a)^(1-epsilon) = n^(a (1-epsilon) ) < n^1 . So, it fails for p(n) = n^a for any a such that a >= 1/(1-epsilon)
Wow. Complexity class separations are really really rare.
Can an expert in sat solving comment if there's any immediate applications of the method from the paper? Or is SAT solving in general pretty far away from worst-case times, and this is a theoretical algorithm which would be hard to apply in practice.
SAT-solving expert here. No immediate applications (the results in the paper are "galactic"). The main question is whether some ideas here will snowball into other ideas, one of which could eventually be very practical.
What do you mean by "galactic"?
Galactic algorithms have such huge constants they figuratively need a galaxy-sized computer and/or galaxy-sized problem, to have any advantage over the normal solutions. Imagine a generic sorting algorithm in O(n) that had a constant of 10^92 **. Technically superior but in practice unusable.
** Yes, I know that's proven to be impossible.
You can use Radix sort https://en.wikipedia.org/wiki/Radix_sort to lower the memory requirement for limited bit-width integers. But there are more practical o(n log n) methods for sorting integers.
Right, that's why I wrote "a generic sorting algorithm". Your case adds the integer limit which allows it to avoid O(nlogn) minimum.
This is a complete non-sequitur, but I checked out your web page. I love the Curious George image. My daughter has been deeply into the Curious George episodes for the past couple of months, and I don't think I've seen him show up in many other places besides kids' shows :D
Such a good show. My kids grew up on it!
Do we know they are galactic?
The data you put into a SAT solver has substantial effect on it's performance in practice. Real world inputs tend to be much nicer than pathological ones, so I don't think there's much practical application, but I also haven't read the paper yet.
I also haven't read ths paper but coding agents absolutely are a part of modern SAT solver coding challenges.
It's surprising that Exponential Time Hypothesis would be false. Quoting a paper from 2022[1]:
> We prove that the time complexity of self-attention is necessarily quadratic in the input length, unless the Strong Exponential Time Hypothesis (SETH) is false[...]
If OpenAI's proof is correct, does that mean self-attention can be implemented in sub-quadratic time? I.e. we could eventually have all the most advanced LLMs running on cheap hardware? To put it more playfully, is ETH being false actually bearish for Nvidia?
No, SETH implies quadratic time does not mean !SETH implies !quadratic time.
but you're telling me.... there's a chance
This but unironically.
put a number on your probabilities. there's a chance you have an aneurysm in the next few minutes and fail to see my comment. if so, oh well, i tried.
SETH is a much stronger claim than ETH
Not relevant, because !ETH => !SETH
What is relevant is that the logic goes the other way: SETH implies quadratic, !SETH implies nothing.
Right, so a refutation of ETH would also refute SETH.
Yes, it's one strong stronger.
It's playful!
But it's also not even wrong, in the Pauli sense.
That makes me wonder if "I see your CS proof, how does this affect LLMs / nvidia stonk price???" being immediately self-described as "playful" ensures criticism looks cranky.
NP looking a little more P than usual
No, this doesn't touch NP ?= P
ETH (which was commonly thought to be true) implies P≠NP.
sure, this proof itself doesn't settle the P/NP problem, but we've lost one of our core beliefs.
At this point, I have no expectations. The future is alien and strange, so time to talk the silicon runes...
What about OpenAI allowed ETH to be determined to be false that couldn't be done by humans? Was there something in particular that OpenAI's AI did that help bridge the gap to a solution?
Higgledy-piggledy,
Exp. Time Hypothesis:
Runtime complexity
Soars to the sky.
Subexponentially,
Tensor contractions have
Tallied solutions for
OpenAI.I wonder how long it'll pay for frontier labs to use compute this way?
I'm reminded of the Apollo program that was cool for a while, but eventually the public lost interest.
Maybe it becomes cheaper? Maybe other labs want to prove their worth will pick up the slack when another loses interest?
the presumption is that these results are a side-effect of reinforcement learning to make the models smarter.
Uh no, reinforcemnt learning doesn't magically pop out math proofs. OpenAI has a ton of mathematicians on staff and is spending millions of dollars in compute to pursue these solutions.
That's not necessarily incompatible. The raw output could come from RL rollouts where the model learnt from the process of solving these problems.
Double-checking, is this more like the recent DFT improvement where even the word-RAM model of computation doesn't justify the fraction of a log factor they eliminated because of an assumption of arbitrary-precision arithmetic, or has ETH actually fallen with the Lean proof being formulated appropriately? Do we know yet?
The DFT result isn't RAM specific. It holds up in multi-tape turing machines. (it is, however, galactic).
This seems huge, like not quite p=np but in the same league. Am I missing something ?
[deleted, originally wrote the hypothesis being true would imply NP=EXPTIME which is wrong, since there can be problems in EXPTIME which aren't in NP.
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.]
> Instead we now know that NP is a strict subset of EXP (there are problems in NP that can be solved in subexponential time).
It's a bit more complicated than that, if you want to be careful. Sorting is in both NP and EXP and can be solved in subexponential time.
I think what they proved is that no problem in NP takes exponential time to solve. (Because you can always reduce them to SAT in polynomial time, and then solve SAT in subexponential time.)
EDIT: apparently the runtime bounds they gave here don't survive the usual polynomial reductions, thus they haven't proven that NP != EXP, it seems.
I mean the result that k-SAT cannot be solved in 2^{o(n)} clearly would imply P!=NP, but how does ETH imply NP = EXP? And how does \neg ETH imply NP != EXP?
If I am understanding this correctly (and I am still reading this!) and if this is true, this means NP is sub-exponential. Sub-exponential does not mean P=NP. But yes, this is huge if true.
This means hard problems aren't as hard as we thought, and it's still possible P=NP. If it turns out to be true P=NP, we're a little closer to that. (I hope P!=NP!)
Every paper which assumes ETH is true might now have their conclusions be disproven.
It doesn't imply NP is sub-exponential, only that 3SAT is. Conversions to other problems can still end up exponential.
No. NP is always poly time reduceable to 3SAT
OTOH, it would be surprising if this sort of technique didn't apply to other NP problems.
Your "No" is wrong. As he said, "Conversions to other problems can still end up exponential", so (NP is poly time reduceable to 3SAT + 3SAT is sub-exponential) does not imply that NP is sub-exponential -- the cost of the reduction may be enough to push the conjunction from sub-exponential to exponential.
Note https://news.ycombinator.com/item?id=50253213 which explains it better.
Subexponential(poly(n)) may be exponential in n
practically, a poly-time reduction can increase teh size of hte problem instance. So maybe you transform a 3-color instance (graph on n vertices) into a n^2 sized SAT instance. You can then solve this in time 2^{n^2 / sqrt{log{n^2}}}, but this is not sub-exponential.
Did you reduce in the wrong direction or am I misunderstanding what you're trying to say?
This defeats a few hypotheses that were widely relied on.
strong exponential time hypothesis, and the titular exponential time hypothesis
It's not saying that these problems are easy, but it does demonstrate that they are much easier than previously believed. A decade ago if a human had published this kind of thing, and importantly if it held up, they would be almost certainly a strong candidate for some sort of award(s).
Assuming P != NP (and that this NP != EXP proof holds up), what's the next most "natural" candidate for how fast NP must grow? This paper appears to show Omega(2^(n/sqrt(log(n))) with a couple additional fudge factors which would be a very disappointing answer.
This is not a proof that NP != EXP. NP is poly time reduceable to 3SAT + 3SAT is sub-exponential does not imply that NP is sub-exponential -- the cost of the reduction may be enough to push the conjunction from sub-exponential to exponential.
Note https://news.ycombinator.com/item?id=50253213 which explains it better.
Definitely puts some weight on the P=NP side of the scale!
My (very amateur) interpretation is that this weakens confidence in P!=NP. Would like to hear from some experts in this area, if this is so or not.
Scott Aaronson comments on his blog "Given this news, I’ll up my personal probability of P=NP from 3% to 5%." (https://scottaaronson.blog/?p=10239#comment-2042428)
I’m not as smart as Scott but for me it’s more like 10% -> 20%. Do we have a prediction market for this?
It seems highly irrational to bet that your evaluation is more likely than Aaronson's.
Why must prediction markets have a predefined end date?
This proves that EXP != NP, which was a stronger claim than P != NP.
In a way it shows that NP is perhaps less distant from P than imagined. Whether it can be _reduced_ to P in some gigabrain way, or whether that can be shown to be impossible remains to be seen.
It is definitely progress towards an answer to P ?= NP.
This is not a proof that NP != EXP. NP is poly time reduceable to 3SAT + 3SAT is sub-exponential does not imply that NP is sub-exponential -- the cost of the reduction may be enough to push the conjunction from sub-exponential to exponential.
Note https://news.ycombinator.com/item?id=50253213 which explains it better.
There's a chain of classes P, NP(aka Sigma_1), Sigma_2, .., Sigma_n, ... PSPACE, EXPTIME. What we know for sure is that P < EXPTIME, others are unknown (well, maybe this paper adds something to this, time will tell).
It's conceivable that each of them is smaller than the next, but also that e.g. P < NP = all the sigmas < PSPACE < EXPTIME or many other possibilities. I think the general consensus is that it's more likely that there are more inequalities than not, but the fact is that we can't even show that P is less than PSPACE so far, which would be extraordinarily surprising if it were true.
It basically just says that NP is not the same as EXP
This is not a proof that NP != EXP. NP is poly time reduceable to 3SAT + 3SAT is sub-exponential does not imply that NP is sub-exponential -- the cost of the reduction may be enough to push the conjunction from sub-exponential to exponential.
Note https://news.ycombinator.com/item?id=50253213 which explains it better.
Subexponential time still can mean much larger than polynomial time. There's a huge space between the two.
It’s not that it isn’t quite p=np; it actually isn’t p=np.
Still, an impressive accomplishment.
no. It's huge.
Can someone ELI5 ETH for those of us who slept through theoretical CS classes? Asking for a friend...
I like this https://www.reddit.com/r/explainlikeimfive/comments/33fmrq/e...
In computer science, the satisfiability problem is the task of determining whether a boolean problem can be satisfied, that is, made to be true, by some combination of inputs. For example, the expression: A AND NOT B is satisfied whenever A is true and B is false, while the expression: A AND NOT A cannot be satisfied.
A naive approach to satisfiablilty would be to check every possible input and see if the expression evaluates to true.
However, the number of combinations that must be checked is 2n, where n is the number of variables in the expression. This is what is meant by exponential time.
The exponential time hypothesis conjectures that you cannot do better, that is, the number of operations needed to solve satisfiability will always be exponential in the size of the problem, no matter what algorithm is chosen.
If this hypothesis is true, it would imply that P≠NP, because satisfiability has been shown to be in NP, and in order for it to be in P there would have to exist an algorithm that solves it in polynomial time.2n should read as 2^n
Unless OP already solved p=np...
that threw me, thanks
> the number of operations needed to solve satisfiability will always be exponential in the size of the problem, no matter what algorithm is chosen
A common complexity theory misunderstanding is that statements like this applies to all or even most instances-- and it leads to objectively bad engineering of the form "oh look this is actually 3sat, it's unsolvable".
(Great fodder for a midwit meme: idiot and genius say "my heuristics go brrr!"-- midwit says "No no no! NP problems can't be efficiently solved!")
Any specific instance may be efficiently solvable (and perhaps all instances coming from your particular problem set -- a subset of all possible 3sats).
So I would add to that paragraph "at least for some 3sat instances".
My 2nd grader once brought home a homework sheet with some simple problems involving combinations of coins and I was like "this is unsolvable!"
There's a set of problems that are (it is conjectured) easy to verify but hard to solve. One of them, called 3SAT, looks for values (a, b, c, ...) such that an expression like ((a or b or c) and (b or not-c or e) and ...) evaluates to true. And it turns out that all of these supposedly hard problems can be converted to 3SAT, so if you find a solution to one you find a solution to all.
The Exponential Time Hypothesis in effect says that 3SAT can only be solved by brute force--trying every possible combination until you find the right one. If your 3SAT expression has 100 variables, then this will take about 2^100 tries (exponential time).
What they found was an algorithm faster than brute force. 3SAT is still potentially one of these hard problems, but finding anything faster than brute force is a major advance.
The exponential time hypothesis is essentially that NP-complete problems' best solutions are all exponential.
NP-complete problems are essentially those where you need to make some kind of choice over a superlinearly-growing set of options where each option can be solved in polynomial time. Like, for example, finding a route between cities on a map under a certain total distance. You might need to go over all choices of routes.
The ETH essentially assumes that the best solution (in terms of complexity, i.e. how it grows) you can get for these kinds of problems is exponential. OpenAI just proved that this is false, you can have solutions that are below exponential complexity (but still above polynomial - if anyone finds a polynomial solution then we'd have proven that P=NP)
> NP-complete problems are essentially those where you need to make some kind of choice over a superlinearly-growing set of options where each option can be solved in linear time.
Seems like a weird way to describe NP, and I'm not even sure it's true?
NP is the class of decision problems where if the answer is YES and someone slips you a hint, you can solve them quickly (or quickly figure out that the hint was useless and report that). Where quickly means in polynomial time.
There's nothing about linear time in the classic definition.
Sorry, you're correct. I meant "polynomial" rather than linear.
NP = nondeterministically polynomial. i.e. if you could evaluate all choices in parallel (or just "know" the right choice), then you'd get a polynomial runtime. That's what I was trying to informally hint at, but I ended up using the wrong term. I'll edit my original post.
That's equivalent to your description - the "hint" is knowing which of the options to choose.
The reason why superlinearity comes into play is that if you had a linearly growing amount of solutions to test then you'd just have a sum of polynomials, which is itself polynomial.
Ok, I read your edited comment. Looks a lot better know.
One nitpick: I think your set of options needs to grow a lot faster than just superlinearly, I suspect it needs to grew superpolynomially?
However otherwise what you describe is essentially true of all problems in NP, not just the NP hard problems:
Sorting is (trivially) in NP, and you can say that to sort you need to pick one out of n! many permutations (which certainly grows superlinearly and even superpolynomially).
NP hard problems have the distinction that if you solve one of them efficiently, you can solve all of them efficiently, because you can reduce them to each other. (Basically because NP hard problems allow you to sort-of describe a computer, and reducing them to each other is equivalent to writing an interpreter or compiler.)
the language around complexity domains is really confusing.
P means "this problem can be solved in polynomial # of steps relative to the problem size"
NP means "we don't know if the problem can be solved in polynomial # of steps relative to problem size, but we know we can check if the result is correct in a polynomial # of steps relative to the problem size"
!ETH: it was widely suspected that the flagship problem in NP, 3SAT, requires an exponential # of steps relative to problem size. We now know that 3SAT requires AT MOST something more than polynomial but strictly less than exponential to solve.
"P = NP" means "if you can check it in polynomial time, there's some way to solve it in polynomial time". "P != NP" means "there are some problems checkable in polynomial time for which there is no polynomial way to obtain the result"
Today's new proof makes "P = NP" "feel more likely", because we know that the flagship problem in NP is not exponential.
This isn't quite true, problems in NP can still require exponential time to solve.
Solving an arbitrary NP problem looks like first reducing that problem to SAT and then solving the equivalent SAT problem. We know (via the Cook–Levin theorem) that any NP problem can be reduced to SAT in polynomial time, and we now know that solving SAT is subexponential in terms of the size of the SAT problem, but it's possible for the conversion to SAT to grow the problem enough that it's exponential in terms of the original problem.
thanks for the correction. Corrected.
3SAT can't be solved in sub-exponential time
Fwiw never thought it was a well-named conjecture
*Can be solved
This proves that EXP != NP
This is not a proof that NP != EXP. NP is poly time reduceable to 3SAT + 3SAT is sub-exponential does not imply that NP is sub-exponential -- the cost of the reduction may be enough to push the conjunction from sub-exponential to exponential.
Note https://news.ycombinator.com/item?id=50253213 which explains it better.
I'm stating the conjecture as requested
How is "This proves that EXP != NP", which is false, a layperson-friendly explanation of the actual proof that 3SAT is sub-exponential?
Whenever someone asks for an ELI5, there's always got to be somebody who further confuses the issue.
Which is a separate issue than the one you commented originally
If I can "count the satisfying assignments of a k-CNF in subexponential time and polynomial space", could I just count the the solutions for assignments of 0 and 1 to x_1, then proceed with whichever is greater (or nonzero), counting the solutions for x_2=0, and so on.
Doesn't that lead me to an existence proof (i.e., a solution) to a k-SAT problem in N*(subexponential_time and polynomial_space)?
And with constant folding, N is reduced by 1 on each iteration.
What obvious thing am I missing here?
This construction splits the space into 'small' models with a quadratic lookup cost and 'large' with sub-exponential cost. The small one is by enumerating all SAT problems with their answers, then looking up the answer. The large one is something in polynomials I don't understand. An answer from openai about where the cutoff is was:
the constructed lookup machine has vastly more states than the estimated total number of physically distinguishable configurations of the observable universe.
So on balance, if this is considered proof that the exponential time hypothesis is false, and openai model reading of the lean was vaguely on point, then I reject the axioms of this system. Not a proof, even if there is lean. I'm OK with being downvoted for that position.
We are living in such a weird, amazing, and miraculous time. It’s completely surreal.
Perhaps this will be the push we need to finally, seriously consider the possibility that our formalisms of “efficient” and “efficiently verifiable” algorithms correspond to nothing resembling reality, and P \in NP is actually ill-posed.
This has been marginally debated since the mid 90s, when Impagliazzo published the “5 worlds” survey. Occasionally it is brought up in talks about average case analysis. There is occasionally a workshop about it. But it has never really got the attention it deserved. How many more of these results do we need to take it seriously? (Assuming we do indeed certify it.)
> Perhaps this will be the push we need to finally, seriously consider the possibility that our formalisms of “efficient” and “efficiently verifiable” algorithms correspond to nothing resembling reality,
What do you mean? Do you mean that our heuristics shortcuts of treating P as efficiently solvable (and NP as efficiently verifiable) are not warranted? So far pretty much all algorithms in P that we found have small exponents. That hasn't changed, but it might change in the future.
Or do you mean something else?
Keep in mind that even most instances of many NP hard problems can be solved very efficiently in practice, because most instances ain't hard.
However we know problems that are expected to be 'easier' than NP that are hard to solve in practice. These are pretty much all the problems we build cryptography out of, because essentially these problems are in the intersection of NP and co-NP and that's expected to be smaller than NP. And cryptography has to be hard to break on average to work: a random key needs to be a good key.
> and P \in NP is actually ill-posed.
Oh, that's very simple to answer: P is not an element of NP. The question people care about is whether there's any element in NP that's not in P. In LaTeX notation P \subset NP vs P \subseteq NP.
I'm not sure what you mean by ill-posed? The question is very clear. What are you trying to say?
"Ill-posed" here means that the formalisms we've chosen to represent "efficient" and "efficiently verifiable" algorithms could turn out to not correspond to anything humans would consider meaningful ("we posed the problem poorly"). For most people, a solution to an NP-complete problem that's barely-subexponential would be clear evidence of these formalisms being ill-posed.
There are many ways it might turn out to be ill-posed, this is just one of them. Impagliazzo's "5 worlds" survey is in some sense a catalog of some of these ways, and includes some of the ways you seem to be referencing (approxmations, probabilistic techniques, average-case efficiency; depending what you mean this could lie in the "Heuristica" world).
> "Ill-posed" here means that the formalisms we've chosen to represent "efficient" and "efficiently verifiable" algorithms could turn out to not correspond to anything humans would consider meaningful ("we posed the problem poorly").
OK, that's a reasonable worry and one that practitioners share. Thanks for explaining. Though I don't think ill-posed is a good term for this, the technical meaning of the term points in a different direction.
So far, as far as I can tell this new result gives much of any extra credence to that worry.
It is completely acceptable in math to use "ill-posed" to indicate that something is insufficiently specified, improperly formulated, or ambiguous. Math people do this all the time.
wtf......
I'm not the kind of programmer that even understands P=NP, so I'll either be way off base, or be blessed with an outsider perspective.
Considering that no human will be able to sift through these in no less than a team-decade, to verify that there's no mistake, yet still that will be massively less compute than the one necessary to produce the 'solution', isn't the empirical finding contrary to the theoretical finding being suggested? Namely that in practice we are generating these 'proofs' in a massive amount of compute time, but it will take tiny amounts of time to verify them.
Is it very useful to talk about computing in purely mathematical terms and not in empirical terms? There's very obvious truths that we are seeing here, and it seems like those that go through some sort of rigorous mathematical training kind of fail to see it. Similar to how 70% of physicians or something believe in the Many Worlds Interpretation or that time isn't real, a sort of algebraic psychosis where one is removed from a human reality that we have access to in order to attempt getting close to an 'objective reality' that is far removed from the human experience.
To some extent we are computing entities, so I don't even think that we can conceive of computing as decoupled from ourselves[1]. I know the observer effect is very often mis-cited by laymen, but I'll be damned if some computer scientists like Godel don't sound like they were up to something similar to this.
Also, here's another outsider perspective. This is obviously slop, I'm not sure how but it's obviously nerd-sniping the CS majors that understand this, because it's obviously very hard to find the flaw, but it gives epicycles energy. It's also sufficiently complex that under a bayesian analysis it is more likely that the AI has reached the limit of its processing power until it becomes confused enough to believe it has reached something significant, kind of like how I'm doing now.
[1] xkcd://1163
[flagged]
math major here, I can't read the paper for shit
Not a math major here. But is this paper way too long? So long that it raises the possibility that OpenAI's staff mathematicians passed through AI's raw output as-is?
That problem seems independent of the 'stochastic parrot' accusation?
A parrot might squeak the theory of everything and it won't matter to any of us cause nobody speaks parrot.
Yes we can just train llms against it and it's all solved. Just a few more trillion dollars and a bunch of deforestation for datacenters bro.
[dead]
It is just that we never considered how advanced stochastic parrots could be so powerful when dealing with basically the whole library of acquired human knowledge and guided by experts to generate.
It is not a demerit, actually I think that it is a very elegant outcome how many problems could be solved by generation and this probably show us how language is a far more important thing than we ever thought it was.
Is this really as interpetable math is fundamentally. Like wtf is this accessibility? who is this for? Do top mathematicians read this like a chapter book? Absolutely ridiculous they have all this compute and creative resources and cant make something more intuitive to help people understand it more natively
It's a math paper written for mathematicians.
It's not possible for someone who's not a specialist in the field to understand it (unless there are more elementary proofs, of which likely none exist).
It's sometimes okay to look at something, go "this isn't for me", and move on. You don't need to have an opinion on everything.
Even mathematicians take a long time to read math books and articles, especially if they go into the details. They don't read math like you would read a novel.
> They don't read math like you would read a novel.
siting on a recliner making an occasional sensible chuckle while flipping through the pages?
Sometimes hard things are hard.
Actually, no - this is what controllability is all about. Humans have to understand it.
Humans can understand it. Not all of them, because to understanding it, there's a lot of other things you need to understand before.
> Absolutely ridiculous they have all this compute and creative resources and cant make something more intuitive to help people understand it more natively
OpenAI has that too - open their website and ask.
I agree with you insofar that the primary motivator for these press releases is public relations and investor confidence, so it should be made as minimally hard to understand as possible just by sheer virtue that it exposes oAI to more cash thrown at them.
I totally disagree with you on the precept that all difficult to understand things need be needlessly dumbed-down/watered-down until palatable for a mass (average) audience. Requiring 'math50' before 'trig101' isn't gate-keeping in any moral sense, it's an effort to save everyones' time involved when the effort is futile.
Similarly I don't demand that haute couture fashion companies explain the style to me until 'I get it' ; I just take it for granted that i'm not going to be able to understand the entirety of the world in one lifetime.
for context (ai convo):
You're right, and I should correct my earlier phrasing. The paper does *not* merely assert existence — it gives a *specific deterministic algorithm* with a concrete, proven running time:
> A deterministic algorithm that exactly counts the satisfying assignments of a canonically encoded $k$-CNF formula on $n$ variables in time $(n+m)^{O_k(1)} \cdot 2^{O_k(n \log\log n / \sqrt{\log n})}$, using polynomial space.
The Lean formalization proves this bound. So it's a fully specified algorithm, not just "there exists one." My earlier "theoretical existence statement" framing was wrong.
*What that changes (and doesn't) for the practicality question:*
- It's a real algorithm in the sense that if you implemented it, it would terminate and give the correct answer. The proof guarantees the bound. - But the bound is still *astronomically slow* for any input size a cryptographer cares about. At $n = 1{,}000$ variables the exponent is already $\sim 1{,}000 \cdot 5 / 5 \approx 1{,}000$, i.e. $2^{1000}$ — far beyond any feasible computation. - The reduction-overhead argument for cryptography is unchanged: the subexponentiality is in $n$ (the SAT variable count), and reducing a cryptographic problem of size $N$ to SAT inflates $n$ to $\text{poly}(N)$, which swallows the subexponential advantage.
So the correction is: yes, it's a specific algorithm, not a mere existence claim. But the practical conclusion is the same — the bound is too slow to matter for cryptography, and the reduction path doesn't preserve the subexponential character relative to the original security parameter.
There are hard problems where the worst case may be exponentially hard, but the average case is much faster. Linear programming and the traveling salesman problem are like that. The faster approaches are considered "probabilistic solutions".
In cryptography, most of the problems believed to be exponentially hard, such as factoring, don't have proofs of an exponential lower bound. There's some risk of a breakthrough that makes those problems easier. A probabilistic solution would be good enough to break many cryptosystems.
I suspect that people at the cryptanalysis agencies worldwide are staying up late tonight, trying to figure out the impacts and risks of this new result.
Incidentally, Ryan Williams says (https://x.com/rrwilliams/status/2114891838377320784):
> In fact, one of the first things I wanted OpenAI to check is that no existing cryptosystems are compromised by the result. Apparently they are safe...
so if you trust his trust of OpenAI, then this has no (immediately obvious) bearing on cryptosystems for now.
Part of the problem with the current centralization of the world's math capability within AI labs is that if they do find that P=NP via an efficient algorithm, it could have implications on all modern public key based cryptography. So it's not completely clear that they will (be allowed to) release these results.
> it could have implications on all modern public key based cryptography
Here's a nice low-budget scifi movie about this:
https://en.wikipedia.org/wiki/Travelling_Salesman_(2012_film...
https://www.youtube.com/watch?v=OgeyHkP6i3g (full movie)
> if AI frontier labs do find that P=NP via an efficient algorithm, it could have implications on all modern public key based cryptography.
The fact that other math problems are bulk solved yet nothing from cryptography was released/published as solved could be a strong indicator that "all modern public key based cryptography" could have been at risk.
Or it could indicate that more resources have been put into cryptography than most other math fields, so AI hasn't yet caught up to our progress.
The 2012 movie "Travelling Salesman" is a thought provoking film that explores this scenario.
I think a proof of P=NP via a galactic algorithm is far more likely than a proof of P=NP via an efficient algorithm.
I mean if someone develops an O(n^100) algorithm for solving an NP-complete problem, that would prove P=NP, but pose no immediate threat to cryptography.
It increases risk, in that a galactic algorithm increases the odds that an efficient algorithm exists waiting to be found, but it is entirely (epistemically) possible that the galactic algorithm exists but the efficient algorithm doesn't.