A New Map Traces the Limits of Computation

https://www.quantamagazine.org/20150929-edit-distance-computational-complexity/

by ernesto95 • 11 years ago

57 39 11 years ago

quantamagazine.org

bru_• 11 years ago

Cool, I did not know that SETH and PvNP were different

thomasahle2• 11 years ago

Basically:

- If you can solve k-sat in time (2-eps)^n, you've refuted SETH.

- If you can solve 3-sat in time (1+o(1))^n, you've refuted ETH.

- If you can solve 3-sat in time n^O(1), you've refuted P!=NP.

Since general k-sat is at least as hard as 3-sat, it follows that SETH is the strongest hypothesis (hence the name) and thus the most likely to fall. P!=NP is the weakest hypothesis and thus the most likely of the three to be true.

darkmighty• 11 years ago

is (1+o(1)) essentially anything subexponential but hyperpolynomial?

tempodox3• 11 years ago

Question from the article: “If you have a formula containing variables that can be set as true or false rather than as number values, is it possible to set those variables in such a way that the formula outputs “true”?”

There is a minimalistic web app that answers this question: http://symbolabs.de/symboole

Enter a Boolean expression and chose the Solve or Shrink functionality from the pop-up menu.

j2kun• 11 years ago

You can bet your life this web app doesn't use an algorithm that is both always correct and scales efficiently with the size of the formula.

tempodox3• 11 years ago

I daresay it's always correct but the cost grows somewhat exponentially with the number of variables. Constructs like `(a or b) xor (c or d) ...` are especially obnoxious. XOR explodes exquisitely.

GFK_of_xmaspast• 11 years ago

Anybody can solve a SAT problem, the issue is how easily they can do it.

IIAOPSW• 11 years ago

Pack it up folks. The webdevs have solved P=NP.

tempodox3• 11 years ago

What do you mean?

WhitneyLand• 11 years ago

Great science writing, explaining concepts in an accessible way without homeopathic dilutions of the substance.

itg• 11 years ago

jsprogrammer

oh my god your really not helping

jsprogrammer12• 11 years ago

Neither is your lack of appropriate grammatical structure.

ColinWright11• 11 years ago

I don't often wade into exchanges like this, but here we go.

Firstly, you mean "you're" and not "your".

Secondly, I know many fantastically talented and productive JS programmers who really, really know what they're doing. They use JS either because they have to, or because it suits their problem domain. Your remark is snide, unhelpful, and out of keeping.

Thirdly, jsprogrammer was right. For many problems only a vanishingly small proportion of instances are hard. In my own area - graph three coloring - it's actually quite difficult to produce graphs that are known to be three-colorable, and yet are hard to color. Most of the time, in the technical sense, graph three coloring is easy, even though it is known to be NP-Complete.

So I believe your remark to be unwarranted.

rm_-rf_slash• 11 years ago

Haters gonna hate, I actually enjoyed quite a laugh from this comment. Just because some people can't take a joke doesn't mean they're opinions count for everyone.

dang• 11 years ago

We detached this comment from https://news.ycombinator.com/item?id=10305170 and marked it off-topic.

A New Map Traces the Limits of Computation

Related Stories