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

25 points by doener 3 hours ago on hackernews | 22 comments

marcusverus | 3 hours ago

peri-cl | 3 hours ago

Also

https://news.ycombinator.com/item?id=50251661 ("The Exponential Time Hypothesis Is False [pdf] (github.com/openai)", 309 comments)

eqvinox | 2 hours ago

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 | 2 hours ago

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

bitwize | 2 hours ago

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.
Old news and the ETH proof has literally no implications for P vs NP or anything else even remotely practical

origini | 2 hours ago

Its still a major breakthrough and challanges a fundamental assumption people had.

yes its old news though.

Your way you wrote your comment feels very dismissive to this result somehow

1234fdas | 2 hours ago

Have you read TFA? It misrepresents the impact on P = NP.

origini | an hour ago

Yes and I don't think it does.

"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

> Old news

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

IPO bait

atleastoptimal | 2 hours ago

HN anti-AI derangement syndrome. Is it realistic to imagine that the NYtimes, which sued OpenAI, running a PR op for OpenAI?

1234fdas | 2 hours ago

The IPO is Anthropic in two days and this result boosts the IPO, even when Anthropic is a rival.

origini | 2 hours ago

OpenAI doesn't has its IPO.

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

pg calls it the Submarine https://paulgraham.com/submarine.html

I wonder how much it costs now to appear in a news segment? Ads are everywhere.

12391827 | 2 hours ago

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?

origini | 2 hours ago

AI is the current frontier research and development with a unique never seen before progress.

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

Who was this written for?

unrented7977 | 2 hours ago

IPO investors

dekhn | 2 hours ago

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 | 2 hours ago

And then on the front page:

> Baidu, Xiaomi CEOs warn of growing gap between AI hype and returns

ChrisArchitect | 2 hours ago

3 week old news OP;

Discussion on source at the time: https://news.ycombinator.com/item?id=50251661