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.""
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.
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?
If they had instead found that it were true, it'd prove P!=NP (since 3SAT is in NP and proving ETH would imply it can't be solved in polytime)
Instead we now know that NP is a strict subset of EXP (there are problems in NP that can be solved in subexponential time). And in fact they provided a constructive proof that 3SAT (and thus any problem in NP) can be solved in subexponential (but still super-quasipolynomial, let alone polynomial) time.
Edit: 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.
> 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?
It doesn't that was my mistake, since edited to remove the part about implying NP = EXP for ETH were true.
But with the hypothesis being false, NP being a strict subset of EXP does 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.
See this from the paper: "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."
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.
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.
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.
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.
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.
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 linear 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.
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.)
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 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).
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.""
Can you explain more?
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.
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
No, SETH implies quadratic time does not mean !SETH implies !quadratic time.
but you're telling me.... there's a chance
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.
This but unironically.
SETH is a much stronger claim than ETH
This seems huge, like not quite p=np but in the same league. Am I missing something ?
If they had instead found that it were true, it'd prove P!=NP (since 3SAT is in NP and proving ETH would imply it can't be solved in polytime)
Instead we now know that NP is a strict subset of EXP (there are problems in NP that can be solved in subexponential time). And in fact they provided a constructive proof that 3SAT (and thus any problem in NP) can be solved in subexponential (but still super-quasipolynomial, let alone polynomial) time.
Edit: 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.
> 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.
Can you explain more wrt the last edit?
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?
> ETH imply NP = EXP
It doesn't that was my mistake, since edited to remove the part about implying NP = EXP for ETH were true. But with the hypothesis being false, NP being a strict subset of EXP does 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
See this from the paper: "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."
OTOH, it would be surprising if this sort of technique didn't apply to other NP problems.
Oh that is interesting and surprising, thank you for highlighting this.
Subexponential time still can mean much larger than polynomial time. There's a huge space between the two.
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.
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.
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.
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?
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.
It basically just says that NP is not the same as EXP
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...
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.
I like this https://www.reddit.com/r/explainlikeimfive/comments/33fmrq/e...
2n should read as 2^n
Unless OP already solved p=np...
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 linear 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.
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
I'm stating the conjecture as requested
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.)
NP looking a little more P than usual
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).
Sometimes hard things are hard.
Stochastic parrot truthers in shambles.
math major here, I can't read the paper for shit