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.
No worries! We're largely a self moderated community. You are no where near the bad end of the spectrum, in fact, your reply to this is atypical and appreciated!
