HN

Comments (136)

• Menu

  svat
  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.
• Menu

  cochne
  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.
• Menu

  criemen
  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.
• Menu

  strommec
  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?[1]: https://arxiv.org/abs/2209.04881
• Menu

  qgin
  NP looking a little more P than usual
• Menu

  softwaredoug
  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?
• Menu

  lisper
  This seems huge, like not quite p=np but in the same league. Am I missing something ?
• Menu

  mlmonkey
  Can someone ELI5 ETH for those of us who slept through theoretical CS classes? Asking for a friend...
• marshray
  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?
• nemo44x
  We are living in such a weird, amazing, and miraculous time. It’s completely surreal.
• Menu

  antics
  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.)
• kevinwang
  wtf......
• JonChesterfield
  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. I'm not inclined to consider "wrote down all the answers ahead of time, so that's free" as a quadratic time solution to SAT. Nor very convinced by the other half.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.
• TZubiri
  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
• Menu

  baggy_trough
  [flagged]
• Menu

  whattheheckheck
  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
• jaekwon
  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.