logoalt Hacker News

jibalt • today at 4:23 AM • 0 replies • view on HN

But even if every problem in NP is sub-exponential (which, as tfpgh notes, this result doesn't prove), how does that make it "more likely" that every such problem is solvable in a polynomial # of steps? I feel like it's a bit like claiming that, because Alex Honnold has shown that a human can free solo El Capitan in less than 4 hours, that makes it "more likely" that I could. To me, his success does not budge the latter probability at all.

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.