YHK - yet another hacker news clone

no. It's huge.

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.

It’s not that it isn’t quite p=np; it actually isn’t p=np.

Still, an impressive accomplishment.

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.

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

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.

Subexponential time still can mean much larger than polynomial time. There's a huge space between the two.

3SAT can't be solved in sub-exponential time

Fwiw never thought it was a well-named conjecture

I like this https://www.reddit.com/r/explainlikeimfive/comments/33fmrq/e...

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

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.

Sometimes hard things are hard.

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

Even mathematicians take a long time to read math books and articles, especially if they go into the details. They don't read math like you would read a novel.

math major here, I can't read the paper for shit

The data you put into a SAT solver has substantial effect on it's performance in practice. Real world inputs tend to be much nicer than pathological ones, so I don't think there's much practical application, but I also haven't read the paper yet.

No, SETH implies quadratic time does not mean !SETH implies !quadratic time.

SETH is a much stronger claim than ETH

Can you explain more?

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

What do you mean? Do you mean that our heuristics shortcuts of treating P as efficiently solvable (and NP as efficiently verifiable) are not warranted? So far pretty much all algorithms in P that we found have small exponents. That hasn't changed, but it might change in the future.

Or do you mean something else?

Keep in mind that even most instances of many NP hard problems can be solved very efficiently in practice, because most instances ain't hard.

However we know problems that are expected to be 'easier' than NP that are hard to solve in practice. These are pretty much all the problems we build cryptography out of, because essentially these problems are in the intersection of NP and co-NP and that's expected to be smaller than NP. And cryptography has to be hard to break on average to work: a random key needs to be a good key.

> and P \in NP is actually ill-posed.

Oh, that's very simple to answer: P is not an element of NP. The question people care about is whether there's any element in NP that's not in P. In LaTeX notation P \subset NP vs P \subseteq NP.

I'm not sure what you mean by ill-posed? The question is very clear. What are you trying to say?