A.I. Just Blew Up a Key Tenet of Computer Science

doener 26 points 22 comments November 17, 2026
www.nytimes.com · View on Hacker News

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

Semantic search powered by Rivestack pgvector
13,334 stories · 126,150 chunks indexed