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

(nytimes.com)

25 points | by doener 3 hours ago ago

25 comments

  • fsmv 3 hours ago ago

    Old news and the ETH proof has literally no implications for P vs NP or anything else even remotely practical

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

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

        • origini 2 hours ago 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 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.

    • undefined 2 hours ago ago
      [deleted]
  • matt3210 3 hours ago ago

    IPO bait

    • chaostheory 2 hours ago 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.

    • origini 2 hours ago 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.

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

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

  • peri-cl 3 hours ago ago

    Also

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

  • dekhn 2 hours ago 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.

  • marcusverus 3 hours ago ago
  • undefined 2 hours ago ago
    [deleted]
  • mbauman 3 hours ago 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 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.

  • eqvinox 3 hours ago 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.

  • FLeXMurphy 2 hours ago ago

    And then on the front page:

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

  • hmokiguess 2 hours ago ago

    Who was this written for?

  • ChrisArchitect 2 hours ago ago

    3 week old news OP;

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

  • 12391827 2 hours ago 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 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?