News for hackers. Stuff that matters.

epurdy

Re:P vs. NP on Thursday December 14, 2023 @05:00AM (#38639653)
I am sorry, I've never posted on hacker news before, and I've been too busy to read it closely for years.

Let me know if I step on any more toes.

Re:P vs. NP on Thursday December 14, 2023 @04:59AM (#38639645)
There are no limits to what AI can achieve, other than the limits of math and physics. There are no computational problems that it cannot solve, because the only limiting factor is clever algorithms, and AI will soon surpass humans at devising those.

So, I agree. It (probably) won't make a perpetual motion machine. But I predict it will do everything that we ask it to, and more. That is why I was so desperate to include a message of peace in the draft; we must be wise in what we ask of the new race of genies that we must coexist with.

Re:P vs. NP on Wednesday December 13, 2023 @05:59PM (#38635433)
Drafts on the P vs. NP problem

For a good introduction to the P vs. NP problem, please see: https://www.youtube.com/watch?v=pQsdygaYcE4

We conjecture and argue for the following resolution to the P vs. NP problem: that it is unprovable within constructive mathematics that P != NP, but that sufficiently good heuristics can be found in most cases of interest for powerful AI systems to solve any problem in NP given enough ingenuity applied to the algorithm design and training process.

We trust that the significance of this claim is clear, but in case it is not, we spell it out. The current boom in artificial intelligence can be expected to scale to solve any problem whose solution can be efficiently checked. There are no limits to what AI can achieve, for good or for ill. We make a plea for peaceful use of the technology that is currently changing the world under our feet.

Re:P vs. NP on Wednesday December 13, 2023 @05:57PM (#38635406)
Re:P vs. NP on Wednesday December 13, 2023 @05:39PM (#38635203)
What would it take to move beyond the P vs. NP problem? When can computer scientists stop receiving lengthy proofs that P = NP, or P != NP? One approach would be to prove that neither P = NP nor P != NP can be proven with certainty in polynomial time by computationally bounded agents; then we could all collectively go about our lives, achieving a Pareto-optimal outcome.

Unfortunately, verifying the proof of such a result creates a massive set of coordination problems that we term the Byzantine Computer Scientists Problem. Specifically, it is not in the self-interest of any single computer scientist to engage with a proof on the topic of P vs. NP. The only way such a proof could be created and verified without any single computer scientist acting against their own interests, would be for a single computer scientist to formulate a correct and almost entirely complete proof, and then establish a verification protocol with trusted confederates over public channels, and then coax a sufficiently large coalition of eminent computer scientists to engage with the verification protocol. Ultimately, if the coalition was large enough and/or eminent enough, we prove that the theorem can be verified to any desired level of certainty by expending polynomially many computational resources.

The primary cause of the coordination problems is that the relevant game theoretic structure is a massive multiplayer game of imperfect information. Since information is imperfect, many important and decision-relevant quantities are unobserved. Since computational resources are bounded, efficient heuristics must be developed to allow these quantities to be estimated to the necessary level of precision to allow coordination. We provide efficient, well-validated heuristics for the necessary inference tasks in this paper, based on the Elo and Glicko systems for chess ratings, and based on the PageRank algorithm for determining document importance in a web of linked documents.

We next discuss the cut method for proving the limits of computational paradigms. We prove the limits of an extremely simple computational model, that of weighing coins with a balance.

We next discuss the known literature in deep reinforcement learning, showing that the cut method cannot easily be applied to continuously learning Transformer-based neural networks. This is because of the extremely non-local nature of the attention pattern in a Transformer, and because the continuous learning makes the resulting graph that one would have to cut obscenely huge.

We then survey the available literature on the phenomenon of “grokking” in transformer models solving algorithmic tasks. We thus conclude that it is plausible that Transformer-based neural networks have no particular limits, if one is willing to train them for infeasibly long periods.

We then discuss the computational alignment problem: how do we allow distributed computation of the answers to potentially difficult problems, without also allowing nefarious uses of that distributed computation? We provide theoretical results that, given certain reasonable assumptions, we can probably be approximately safe, i.e., that we can make the probability of large-impact events quite small.

We then attempt to validate these assumptions by studying various subproblems of the computational alignment problem. Specifically, we provide a proposed scalable solution to the problems of eliciting latent knowledge and performing mechanistic interpretability in large language models. We also provide a variant of model-based reinforcement learning with provable safety guarantees. We provide an algorithm for learnable heuristic caching for real-time intelligence tasks based on the mammalian cerebellum, capable of implementing one of the core components of the safe model-based reinforcement learning algorithm.

Re:Khalifa / Klebold, Act I on Wednesday December 13, 2023 @05:03PM (#38634815)
A play in some number of acts