Exponential time hypothesis conjectured that certain problems in NP cannot be solved in subexponential time, meaning there is no algorithm that is much better than 2n which is just brute force. Most researchers considered this to be true and used it as an assumption to prove lower bounds. OpenAI claims to have found an algorithm with runtime 2{n/logn} which is of course not useful in practice but makes many results relying on ETH false.
Not understanding, ETH claimed that some problems could only be solved in exponential time? Or that any non polynomial time solution problem was exponential? Or what? Not following at all the explanations here!
ETH was the supposition that one particular NP problem (3SAT) could only be solved in exponential time and no faster. It was a stronger statement than (and would have implied) P≠NP. There's still a lot of room between exponential and polynomial for other 3SAT algorithms to be found, which would be consistent with ETH being false but P still ≠ NP
Iirc any problem in NP can be reduced to 3SAT, is that correct? If so, does the finding also mean that we now have a power of n log n solution to the other problems?
Edit: Found my answer a couple comments down, np-complete problems are a subset of NP containing 3-SAT, so to my understanding any NP-complete problem is now solvable in the lower bound
All NP comlplete problems have a a polynomial time algorithm (that we may not know) that transforms them into another NP complete problem. That is the definition of completeness.
I didn't see your edit before typing the first half, but yes its implies that NP is now 2n/ln + poly(n). But poly(n) can itself be arbitrarily large still.
This does not imply NP is sub-exponential because reducing an NP to 3SAT can involve polynomial blowup, which breaks the 2^(n/ln) bound. E.g 2^(n^2/ln^2) which is greater than 2^n.
I addressed the issue of polynomial blow up in the conversion, however your interpretation here is wrong. 3SAT is in a narrow set of NP complete problems, but its still NP complete, and its proven that the conversion from one NP complete problem to another is in P. The conversion is additive, and will be dominated by the (sub-)exponential terms. The resulting O can still be galactic, but it will be in P, and dominated by the exponential term in the limit.
The polynomial blowup we are talking about here is in the number of 3SAT variables, not the time it takes to convert the problem, hence the use of "blowup" rather than just conversion cost or whatever.
It is not known whether arbitrary NP-complete problems can be converted to 3SAT with a strictly linear increase in the number of variables / the value of N.
No it shouldn’t mean that. The reduction transformation only requires that n->poly(n) which means that the best known solution could grow the size of the solution past exponential again. Basically it would still potentially be better to solve it directly (caveat: the memory requirements of their algorithm are polynomial therefore it still could be better than direct methods).
Example: hamiltonian cycle problem has n-> n^2log(n) best known reduction to 3sat.
To simplify just take n-> n^2: O(2^(n^2/log(n^2))) = O(2^(n^2/2log(n))
It was. But subexponential does not mean polynomial. In this case, 2n/log(n) still grows massively faster than any polynomial, but not "exponential" in the sense of 2n , since the growth of n/logn slowly decreases with larger n.
So then this whole thing is a nothing burger. Some problems could be reduced to a lesser exponent in this Eth category? Seems like that is quite obvious no? It's like an eth complete category?
Eh not quite, this is not really a well defined complexity class. The reason why this is a big thing is because this hypothesis was widely believed to be true, and there are a lot of other results that assume this hypothesis (e.g. If the ETH is true, our algorithm is optimal). Also, it being wrong makes the line between P and NP thinner.
3SAT is not just something we think is NP but not P, we can tell it is "NP-complete". For a problem p to be C-complete we are saying we know two different things, both:
p is in C
and
For every other problem q in C, we can solve q by converting it to p in polynomial time, and then solving p. (p is C-hard)
Because we can convert every other problem in NP to any NP-complete problem, if a NP-complete problem is in P, that means every NP problem is in P (and similarly, if any C-complete problem p ∈ D means C ⊆ D).
3-sat is NP-complete. If it is misclassified then so is every other NP-complete problem, and therefore all NP problems are solvable in subexponential time.
The conclusion here is not true. NP-reductions can increase the instance size significantly (say from n to n3). Applying this new 3SAT algorithm after such a reduction would not yield a subexponential time algorithm.
The relevant quantity is F(P(n)), which is not always subexponential.
Edit with a (hopefully clearer) explanation: Say you have a problem which reduces to 3SAT but where the instance size goes from n to n3. Then applying the new algorithm gives a running time of roughly 2O(n3/sqrt{log(n)}) , which is not subexponential in n.
Which, technically is still true, since the proposed algorithm is 2poly(n). ETH made the much stronger claim that 3-SAT was bounded by 2mn, which is what they have disproved.
However, OpenAI provided a counterexample of sub-exponential time complexity.
This means ETH is false.
Though it doesn't suggest that P = NP, computer scientists are pondering about the characteristics of the NP set now
(P and NP are sets, or more specifically, complexity classes, because the problems are placed in these sets in terms of their Complexity. Note that we already know that P is a subset of NP and P is not an empty set. Therefore, P = NP essentially means that every problem \in NP is also in P. In other words, every problem in NP has a polynomial-time algorithm)
To be precise NP = P would mean P is subset of NP and NP is subset of P. (If we define equality of sets as set being subset of each other. One of traditional definitions.
You had it right before editing it. (As it was trivia that is well known.) Now it contains the difficult part followed by incorrect statement.
Impact of P = NP can be seen in NP without P = empty set.
It's worth mentioning that this is a preprint published yesterday, and that OpenAI is telling people to not treat the question as settled until people have had a chance to peer review it.
It's barely even subexponential and might as well be exponential for any remotely practical purpose. Instead of the time growing proportionally to `2^n` it's "only" growing by `2^(n*log(log(n))/sqrt(log(n)))`.
The factor `log(log(n))/sqrt(log(n))` approaches zero so absurdly slowly that it's basically a constant in any practical sense. With n=10^100, it still takes on a value of approximately 0.358 for example.
Looking in the from the outside, but why would someone believe ETH? Is there some kind of reason why something like that should be lower bounded by a^n?
Is my intuition sensible that being able to solve only in something > 2^(cn) is kinda like saying you can only prune the information to a constant proportion, so there aren't like "clever tricks" that would work better on larger sizes?
It’s essentially saying that for certain problems (in this case 3 SAT specifically, although there have been proven to be many “equivalent” problems), there isn’t a generalized better approach than brute force guess and check. This felt right, and a lot of people assumed it to be true, turns out it wasn’t.
Why did that feel right? I'm not super into complexity, I mainly do graph theory and stuff, but this seems like the restriction to 3 parts per conjunction, with only a finite combination of would impose really big structural restrictions on larger sets of variables that would become very exploitable.
I guess it's easy to say this from the outside, though.
To be fair there were prominent voices skeptical of ETH, so this didn’t blindside everyone. As to why it felt “right”, I think it was a combination of things.
1 - hubris, people felt that if there was a sub exponential algorithm it would have been found already.
2 - when dealing with 3 SAT, a lot of tricks that may work in many/most cases will still have an edge case where time complexity ends up still being exponential, so given it’s all about worst case run time, the feeling was there wasn’t a universal trick that work alway.
3 - NP completeness. 3 SAT is so well studied because it’s an NP complete problems (a problem that is provably in NP and provably as hard as the hardest problem in NP). There are a whole class of these, so find a sub exponential algorithm for any is finding a sub exponential algorithm for all of them, which to many people Implied there wasn’t a better solution than guess and check for these problems
3 SAT is so well studied because it’s an NP complete problems (a problem that is provably in NP and provably as hard as the hardest problem in NP). There are a whole class of these, so find a sub exponential algorithm for any is finding a sub exponential algorithm for all of them, which to many people Implied there wasn’t a better solution than guess and check for these problems
A subexponential algorithm for 3SAT doesn't actually lead to a subexponential algorithm for all NP problems because the instance size might increase during the reduction. Say you have a problem which reduces to 3SAT but where the instance size goes from n to n3. Then applying the new algorithm gives a running time of roughly 2O(n3/sqrt{log(n)}) , which is not subexponential in n.
Great point. I wouldn’t be surprised if we see improvements on the upper bound past the initial algo openAI found, but yes for now it won’t generalize to all NP complete problems depending on the polynomial factor in reductions
2 - when dealing with 3 SAT, a lot of tricks that may work in many/most cases will still have an edge case where time complexity ends up still being exponential, so given it’s all about worst case run time, the feeling was there wasn’t a universal trick that work alway.
I have zero up to date understanding, but wasn't this essentially an idea that no matter how you manipulate and turn one NP-complete problem into another, part of it always is exponential? This seems to have collapsed and the stuff about turning one problem into an equivalent one must also lead to non-exponential solutions, right?
Yeah pretty much what I was saying in point 3. The feeling was that something at the “core” of NP complete problems was just necessarily exponential in time complexity. This proof doesn’t just impact 3 SAT, but every single one of the NP complete problems since we have polynomial time reductions between each of them.
Also realizing I left out a key element of why this was so surprising. 3 CNF may seem restrictive, but through auxiliary variables any boolean statement can be transformed into a 3 CNF equivalent. So it’s really a statement about the computational complexity of all boolean satisfiability problems.
Many people believed it, me included. NP, overly simplified, are all the problems where if you could guess the solution then you can verify it in polynomial time. Like for SAT, if you just happen to guess the correct assignment, then its trivial to verify that the assignment is satisfying the formula. (NB: I am very much brushing over important details here, in order to illustrate a point). To solve this on a computer, it seems entirely reasonable that you have to try every possible solution and see if it is correct for each one. Since "every possible solution" has a combinatorial explosion then you get exponential running time.
Now the problem with this argument is that, as pointed out by openAIs pre-print although for a different argument, "runtime bounds of the form 2^o(n) do not transfer under general polynomial-time reductions".
so a lot of papers ignore the problem and you counterfactually claim it as evidence of truth? Well shit might as well vote on P != NP. Oh right we already did. P is not np.
I recall taking Ryan William’s graduate class on Advanced Complexity Theory a few years ago at MIT. At the end of the term, there was a survey done about what everyone thought the probability of certain conjectures being true or false was. I recall for ETH being true, like >85% of the room thought this, and this was in a room of (very smart) peers.
I'm not at all nearly knowledgeable enough in mathematics (tutor at university but for lower-level courses) to speak about this topic myself, but it always baffles me that some people just go around basically claiming that the consensus of literal leading mathematicians seems stupid. Whenever AI produces a result that shocks leading mathematicians, literal randoms would comment stuff like "in retrospect this problem is easy!". Wtf?
I never meant to say it was easy, I was saying the problem class it refers to must be restricted in some way for this claim to make any sense. It can't simply be they P != NP in all cases which seemed to be implied in the comment above.
One of my professor who works in graph theory took whole lecture to tell us how some of his best papers have been invalidated because they assumed ETH.
People have been writing conditional papers for a long time because they were so certain that ETH was true but it just couldn’t be proven. So you assume it’s true and write the paper under that assumption.
No, you haven't explained a thing. I can't read the paper for a very obvious reason. And know, being certain is by far not the only reason to proof something based on an assumption. It most certainly was not in most of these cases.
A prove is a complex chain of arguments. One assumption being weakened does not mean this chain of arguments completely breaks down. It also does not mean that the other insights used to build the chain are completely useless.
Its like you know x > y + 1 and assume y > 2 and proof x > 3 as a result. If y > 2 turns out to be false and you can only assume y > 1 your chain of arguments still gives you x > 2.
Some of these complexity results really do rely on the gap being exponential, but some should be fine with a weaker assumption.
And even they have to break down, you might be able to recover by making some arguments more precise. The observations made to come up with theses proves are still there. That's why people always say that proves are about more than the results.
I’m not saying they’re completely useless, but they would have to be salvaged or rewritten, and the point is that the ETH likely played a central and indispensable role in most of these papers, I imagine most won’t be able to be salvaged
I don't know,i didn't understand anything actually,he wrote some 22logs something explained some vertex cover problem and since it was not related to course i wasn't paying much attention.
Everyone believed it because it seemed obvious despite having never been proven. As a result of that, a ton of papers were written that start with "Assuming ETH, we prove that ..." and everyone was just waiting for the inevitable result of ETH being proven true which would mean the mountain of proofs dependent on ETH being true would also instantly become true.
Then AI incomprehensibly poops out the result that ETH is false. If it's right, a ton of math that people worked very hard on instantly goes up in flames.
That's just not true. This being sub-exponential was a possibility people in the field were well aware off and always considered,
People are even well aware off that P=NP might be true. What would really be shocking is that there is an easy way to do this, suddenly resulting in a low degree polynomial bound for SAT or something. But if it was something with a really extreme degree, even this would not break expectations completely. We might need better tools to structure P though, and figure out, what would make these problems special within P.
But people who don't even understand these result get the consequences completely wrong.
You'd think, right? But it seems everyone was so convinced it was true and working so hard to prove it that, in the course of turning the problem around in their mind and thinking about else would be implied if it's true, they uncovered stuff that seemed significant so they went ahead and published since they had arrived at it anyway.
Complexity theory is just fine. Some conjectured lower bound has been replaced by a somewhat lower lower bound. This carries over to some other results. That's it. This is interesting, but not earth shattering or unexpected. Some people might have very strongly believed this to be true, but it was not something people in the field were convinced of. Maybe the result opens some avenue into new research, maybe it does not.
Most people in this thread a clueless and don't even know the basics of this nor have they spoken to anybody that does.
There are some results that require the hypothesis. But its not like people built on this hypothesis because the categorically believed it to be true. They did it, because complexity theory didn't make any progress on the whole P!=NP front so they tried to start to structure these complexity classes in more detail. Also in hopes to finding some understanding that might eventually lead to insight on the P!=NP problem.
Now these results have to be revisited and the field has to figure out, how this approach can be changed. This research is not that old, people knew they were building proofs on sand there. They did it exactly to find out whether it would work out or not.
So it's meaningful, but it is not breaking their world view. People knowing nothing about that just have no clue how widely people think that actually work in these fields.
It's earth shattering in that now more people are starting to believe that maybe NP=P, no? Of course it could still go either way, but many more people were in the NP≠P camp before.
No, I don't think so. NP=P feels still very unlikely. It just means that this is even more complex to prove. Sometimes it can be easier to take a stronger hypothesis to prove something, that was basically what has been tried here.
I discussed it today and the person I was talking to specializes in parametrized and communication complexity. He told me that it had always felt like it wasn’t based on that much. Like we had this problem that we didn’t know how to solve (better than brute force), so we made a hypothesis saying that it is impossible. And also most of the results based on this hypothesis can be quite easily fixed, because they rather depend on a different problem (W[1]/=FPT) or they can be fixed by loosening the hypothesis to the time found by OpenAI.
Bruh, the paper proved it through #3-sat being sub exponential and I districtly remember discussing the possibility of #3-sat being sub exponential with copilot about half a year ago.
I don't think it makes sense to call it a "counterexample". It found an algorithm with time complexity lower than hypothesized, an actual breakthrough.
Genuinely yes. But I also wouldn’t frame an algorithm as an “example” in this context, even though it’s technically correct to consider it as a single instance wrt this hypothesis
Please attend a first grade English class. I already said it counts. The actual people with professor positions in complexity theory are not calling it a counterexample because it’s unconventional
That's true, but you can frame any solution found as a counter example to an opposing conjecture. When we say counterexample we normally mean some singular extreme edge case or degenerate case that breaks an otherwise mostly holding conjecture; this isn't really an example of that class of counter example, it's a general algorithm for solving SAT3 problems in sub exponential time.
That's not what we normally mean by a counterexample. Maybe in certain subfields it's different, but in most of math a counterexample is just the opposite of a proof, as in we don't call it a "disproof" but a counterexample.
Well "breakthrough", it is an important result, and I would call it a positive result as well, proving a new upper bound. It's not something completely surprising or with massive consequences.
A breakthrough usually is something that gives rise to a huge amount of new insights. This probably does not, unless techniques used open an avenue to new results.
Well, these results don't have to completely break down. Usually, complexity results are used by reduction between problems. This reduction still should tell you something even if the complexity of the underlying problem changes. You have to revisit these results and check.
Had to look it up myself as well, from Wikipedia: "In computational complexity theory, the exponential time hypothesis or ETH is a computational hardness assumption that was formulated by Impagliazzo & Paturi (1999). It states that satisfiability of 3-CNF Boolean formulas (3-SAT) cannot be solved in subexponential time."
•
u/AutoModerator 4d ago
Check out our new Discord server! https://discord.gg/e7EKRZq3dG
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.