Despite the (literally) bombastic headline, this is a fairly decent explanation of ETH and P=NP for the general public. The one bit it misses, however, is that P=NP doesn't necessarily mean computationally tractable. I fully agree with Talia Ringer here:
> I guess now is a good time to admit this: I've semi-secretly held the strong belief that P = NP but with some wildly impractical algorithm using some kind of stupidly large constant factor somewhere since undergrad back in 2008-2012. I usually only say this in polls
The ETH disproof has this exact nature. The proposed less-than-exponential algorithm is only useful if you have more than 10-to-the-googol-power variables or some absurd number. For anything less the algorithm is exponential.
It was last week! It's "old news" here because it was big news here and is now just trickling into mass market media like the Times.
Also "no implications" to P/NP is not really right. The ETH was a softer requirement for the same problem area as the harder "P=NP?" problem. For years "everyone knew" there were no polynomial solutions to NP problems. And the biggest reason for that is because "everyone knew" that NP problems only had exponential solutions.
Well, everyone was wrong. Now, tell me what consensus understanding is on P/NP. Fuck if I know either. Seems like the ETH result had some pretty clear "implications" for our understanding of the deeper problem.
Its a nytimes article which only shows how long it takes for the normal press to get onto a topic and that someone using hn thought its worth while to share.
What a stupid drivel. Aaronson said that the ETH result raised his own probabilities for P==NP from 3% to 5%. We don't know anything yet.
And why insert AI in the finishing sentence?
“This could lead to better A.I.,” Dr. Impagliazzo said, “in all sorts of ways.”
Of course, this would be the only "improvement". People just cannot stop "thinking" about AI for more than 5 seconds, due to an AI press blitzkrieg just like the one happening here. Can we go back to talking about vaccines every 10 seconds?
From what I can tell, knowing whether P=NP will not have any bearing (direct or even indirect) on any computation that is done today or the near future. I've asked around (amongst a fairly senior set of CS people) and get only highly indirect hand-wavey answers. I am, of course, happy to be set straight.
marcusverus | 3 hours ago
peri-cl | 3 hours ago
https://news.ycombinator.com/item?id=50251661 ("The Exponential Time Hypothesis Is False [pdf] (github.com/openai)", 309 comments)
eqvinox | 2 hours ago
Their source is OpenAI's announcement, which states:
> This work will be verified and shepherded by…
…and we can talk after that has happened.
mbauman | 2 hours ago
> I guess now is a good time to admit this: I've semi-secretly held the strong belief that P = NP but with some wildly impractical algorithm using some kind of stupidly large constant factor somewhere since undergrad back in 2008-2012. I usually only say this in polls
https://x.com/TaliaRinger/status/2107939845788373492
bitwize | 2 hours ago
fsmv | 2 hours ago
origini | 2 hours ago
yes its old news though.
Your way you wrote your comment feels very dismissive to this result somehow
1234fdas | 2 hours ago
origini | an hour ago
"a related conjecture"
"Similar to the argument that P can’t equal NP, the E.T.H. held that certain problems must always remain hard for computers to solve quickly."
It is used as an analogy for layman?
ajross | 2 hours ago
It was last week! It's "old news" here because it was big news here and is now just trickling into mass market media like the Times.
Also "no implications" to P/NP is not really right. The ETH was a softer requirement for the same problem area as the harder "P=NP?" problem. For years "everyone knew" there were no polynomial solutions to NP problems. And the biggest reason for that is because "everyone knew" that NP problems only had exponential solutions.
Well, everyone was wrong. Now, tell me what consensus understanding is on P/NP. Fuck if I know either. Seems like the ETH result had some pretty clear "implications" for our understanding of the deeper problem.
matt3210 | 2 hours ago
atleastoptimal | 2 hours ago
1234fdas | 2 hours ago
origini | 2 hours ago
Its a nytimes article which only shows how long it takes for the normal press to get onto a topic and that someone using hn thought its worth while to share.
chaostheory | 2 hours ago
I wonder how much it costs now to appear in a news segment? Ads are everywhere.
12391827 | 2 hours ago
And why insert AI in the finishing sentence?
“This could lead to better A.I.,” Dr. Impagliazzo said, “in all sorts of ways.”
Of course, this would be the only "improvement". People just cannot stop "thinking" about AI for more than 5 seconds, due to an AI press blitzkrieg just like the one happening here. Can we go back to talking about vaccines every 10 seconds?
origini | 2 hours ago
Affecting already a lot of people around the globe.
And its not just LLMs, its IT Security, future of jobs, mathematical breakthroughs, etc.
Why do you still just hate AI? For AI sakes?
hmokiguess | 2 hours ago
unrented7977 | 2 hours ago
dekhn | 2 hours ago
FLeXMurphy | 2 hours ago
> Baidu, Xiaomi CEOs warn of growing gap between AI hype and returns
ChrisArchitect | 2 hours ago
Discussion on source at the time: https://news.ycombinator.com/item?id=50251661