The Exponential Time Hypothesis Is False [pdf]

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.]

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.

Still, an impressive accomplishment.

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.

Also for NP problems that can't linear reduce to kSAT just having the knowledge that SAT is sub-exponential (and the tools), makes it a lot more likely that we see a whole lot more problems become exponential.

Note https://news.ycombinator.com/item?id=50253213 which explains it better.

NP is not yet proven to be subexponential but still, ETH disproven is huge

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).

Note https://news.ycombinator.com/item?id=50253213 which explains it better.

Note https://news.ycombinator.com/item?id=50253213 which explains it better.

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.

Note https://news.ycombinator.com/item?id=50253213 which explains it better.

It doesn’t matter if I bet $N on something using cash or margin, my exposure is still $N.

Since you can’t have unlimited exposure, this would still lock up capital, until the bet can be resolved.

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.

Fwiw never thought it was a well-named conjecture

This proves that EXP != NP

Note https://news.ycombinator.com/item?id=50253213

Note https://news.ycombinator.com/item?id=50253213 which explains it better.

  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.

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".

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)

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.

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.

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 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.

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.

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.

It seems to me that the logic only goes the other way ... if ETH had been proven then it would follow that P != NP. With !ETH we really don't know any more about P ?= NP then we did before. Reasoning that P = NP is "more likely" strikes me as a form of a fallacy of affirming the consequent.

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).

siting on a recliner making an occasional sensible chuckle while flipping through the pages?

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.

Why? The investors can just ask Claude or Gemini whether the proof holds up.

OpenAI has that too - open their website and ask.

They are making good progress on similar research programmes for many cetaceans.

In the case of our stochastic parrots it's even easier, since they already speak something like human language. And for the math proofs it's even easier, because once they are formalised into something like Lean the humans only need to understand the statement of the theorem, and a mechanical computer program can check the proof.