A.I. Just Blew Up a Key Tenet of Computer Science
doener
26 points
22 comments
November 17, 2026
Related Discussions
Found 5 related stories in 202.1ms across 13,334 title embeddings via pgvector HNSW
- AI Is Powerful Enough to Crack Our Hardest Math Problems–and Kill Us All diogenes_atx · 23 pts · September 12, 2026 · 63% similar
- AI is dramatically accelerating AI research yurivish · 253 pts · November 06, 2026 · 62% similar
- The Exponential Time Hypothesis Is False [pdf] vok · 498 pts · October 26, 2026 · 61% similar
- How An AI math breakthrough ignited a controversy pseudolus · 213 pts · September 09, 2026 · 60% similar
- AI may have solved the most important problem in mathematics vinni2 · 34 pts · November 20, 2026 · 60% similar
Discussion Highlights (10 comments)
marcusverus
https://archive.is/eXSO3
peri-cl
Also https://news.ycombinator.com/item?id=50251661 ( "The Exponential Time Hypothesis Is False [pdf] (github.com/openai)" , 309 comments)
eqvinox
What a silly, pointless article. 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
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 https://x.com/TaliaRinger/status/2107939845788373492
fsmv
Old news and the ETH proof has literally no implications for P vs NP or anything else even remotely practical
12391827
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?
hmokiguess
Who was this written for?
dekhn
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.
FLeXMurphy
And then on the front page: > Baidu, Xiaomi CEOs warn of growing gap between AI hype and returns
ChrisArchitect
3 week old news OP; Discussion on source at the time: https://news.ycombinator.com/item?id=50251661