lobsters score: 33 · tags: math, pdf
It proves that one of {NP ≠ PSPACE, PSPACE ≠ EXPTIME} is true, which is a pretty big deal!
score 2 · canonical
We know that P (the set of problems solvable in polynomial time on a deterministic Turing machine) is a strict subset of EXPTIME (the set of problems solvable in exponential time on a deterministic Turing machine) via the time hierarchy theorem. We also know that
P ≤ NP ≤ PSPACE ≤ EXPTIME
(using ≤ to mean non-strict subset since I’m typing on my phone)
where NP is P but with a nondeterministic TM, and PSPACE is the set of problems solvable in polynomial space on a deterministic TM.
So basically via the time hierarchy theorem, we know that at least some of these have to be strict containment, but we are not sure which.
Before this result, it could have been that P != NP, but NP = PSPACE = EXPTIME; i.e., the jump from P to NP is the only increase in the computational complexity in that set of classes.
Hillel seems to be implying that this paper shows NP != EXPTIME . I’m not entirely sure how he came to that conclusion - I didn’t read the paper thoroughly and it’s been a while since my complexity days, but I don’t immediately see how the stated result applies to those two classes, since k-SAT is definitely a member of NP and is not complete for either PSPACE or EXPTIME.
These questions are interesting because there are many problems in these complexity classes that we don’t know how to solve efficiently, or whether they can be solved efficiently. P versus NP is of course the most well known complexity question, but there are tons of other complexity classes that we aren’t sure how they relate to each other.
score 1 · canonical
I was working off the assumption that 3-SAT is NP-Complete, so if there’s a subexponential algorithm for solving it then there are problems in EXPTIME harder than 3SAT. But this comment on the orange site points out that a polynomial time reduction of something to 3SAT can increase the problem size enough to recreate exponential time-bounds. That’s why the paper says this:
Note that runtime bounds of the form 2^o(n) do not transfer under general polynomial-time reductions (2no(1) would be needed for this), so our result does not imply that general NP problems admit subexponential time algorithms. However we do obtain subexponential time algorithms for counting graph colorings and perfect matchings.
Does this potentially mean that there are can be other shades of “hardness” inside NP-Complete?
score 1 · canonical
I was working off the assumption that 3-SAT is NP-Complete, so if there’s a subexponential algorithm for solving it then there are problems in EXPTIME harder than 3SAT.
Oh, is what you are saying here that if there were to be a subexponential algorithm for solving all problems in NP, that via the time hierarchy theorem there must be a separation between EXPTIME and DTIME(2^o(n))? That makes sense, thanks for clarifying.
Does this potentially mean that there are can be other shades of “hardness” inside NP-Complete?
Hmm, very interesting. I guess there are also different ways of quantifying hardness within NP. I remember learning that there are some NP-complete problems for which even coming up with an approximation is NP-complete. But then it also seems like there’s something potentially significant about NP-complete problems whose reduction to 3SAT involves creating some bounded number of variables and/or clauses, since that would allow the problem to be solved in subexponential time.
I guess either we live in a universe where there is a non-empty complexity class ENPC < NPC (ENPC for Easier than NP-complete) of problems that can be solved in 2^o(n), or NP != EXPTIME.
score 1 · canonical
Typical EXPTIME definition allows polynomial reductions. «Does this program stop in 2(n0.1) steps, for n being the length of the program» is EXPTIME-hard and obviously doable in 2^o(n) steps.
There is an entire field of fine-grained polynomial complexity (distinguishing n^2 from n^3 etc.); it might have lost 3 out of 4 core hardness assumptions in a few weeks, though (and who knows whether orthogonal-vector-pair search is already being checked in Lean somewhere), of course one can do similar study for NP-complete problems, although maybe people haven’t got around to it.
Approximations behave differently for different problems, so it’s a bit of a topic of its own; and it is not even necessarily easy to define approximation version for some cases (even for subset-sum one could negotiate what approximation means).
Oh, and assuming P≠NP there are NP-intermediate problems, not in P but not NP-complete.
score 1 · canonical
This is in addition to other very good comments.
https://arxiv.org/abs/2610.06783 (subquadratic 3-SUM and subcubic all-pairs shortest paths; status: LLM-agent-generated Lean proof, plus a proof explanation from two leading experts in the field) has broken 2 out of 4 main hypotheses in fine-grained complexity (i.e. the study of the exact optimal degree of polynomial algorithms; see https://en.wikipedia.org/wiki/Fine_grained_complexity for an introduction). Strong ETH was the one of the two remaining ones.
score 1 · canonical
From my interpretation of reading the result by OpenAI, they also show this:
In this paper, we refute ETH by giving, for every fixed k >= 2, a deterministic algorithm that counts the satisfying assignments of a k-CNF in subexponential time and polynomial space.
score 1 · canonical
Wow.
Claude Opus 5.5 at high effort can rederive the refutation of ETH from the following condensed description: […one paragraph hint]
“The exponential time hypothesis is false — proof left as an exercise for the reader.”
score 1 · canonical
proof left as an exercise for the reader
Ah yes, when the author channels their inner Fermat.
score 1 · canonical
deleted by creator
What if P=NP but the algorithms are so ridiculously impractical that for all intents and purposes we gain nothing over our current best approaches.
score 1 · canonical
The famed
nlog(n)integer multiplication algorithm involves a 1729-dimensional Fourier transform!
score 1 · canonical
Instead of imitating human mathematicians and presenting long series of definitions and theorems, I think AI should do as 3blue1brown says – “If you encounter a mathematician at a conference, and ask them how their proof works, then they will almost always give you a clearer insight than what’s in the paper”
That is, the papers are written “backwards” from definitions. But the real explanation is how you got there. What thing tipped you off that a certain definition or theorem would be useful in solving the problem, the angle of attack
In other words, we should use AI to do better than the state of the art in as many dimensions as we can, not just perpetuate the same habits
score 4 · canonical
Anthropic’s repository contains a one-paragraph hint about the construction that is allegedly enough for Claude Opus 5.5 high to disprove ETH, I am not fluent in the terminology but it does have the shape of explaining the core idea well to a specialist! So maybe they are doing a step in the right direction there.
score 1 · canonical
“If you encounter a mathematician at a conference, and ask them how their proof works, then they will almost always give you a clearer insight than what’s in the paper”
Adding to this, the valuable insight – the thing you can actually use in thinking – is the compressed form of the knowledge. You’re more likely to get that in a short in-person conversation. The author’s hand is almost forced. “Ah, yes, I basically just realized I could transform the problem using X, and then theorem Y would apply, and I could convert back and conclude Z” or whatever the case may be. The essence of an insight must end up being short like that, because we can’t “think” on the scale of 20 dense pages of equations. The elaboration is an expansion of the insight, rather than the other way around.
score 1 · canonical
You can in fact take the paper and have a great conversation with the AI or have it create your own visualizations and explanations. Particularly with Opus 5.5 it’s a great experience.
score 1 · canonical
Sure, I do that for learning things in my own domain, for things I want to build
But for a general reader, it’s more efficient and interesting for a few people to produce explanations at different levels, rather than having everyone burn approximately the same tokens with AI
In other words, what people are saying is that now that proofs themselves are more plentiful, explaining proofs becomes relatively more important. So my suggestion is around the “explain” part :-)
I don’t think the paper itself is useful for a lobste.rs audience, other than the meta-knowledge that an AI produced it, trained on some unknown data, with some unknown humans prompting it
score 1 · canonical