We don’t know that, P vs NP is an unproved conjecture. Most real world problems are not giant knapsack problems. And there are algorithms that quickly produce answers that are close to optimal. Actually, most of the real use of intelligence is not a complexity theory problem at all. “Is inventing transistors a O(n) or an O(2^n) problem?”
P vs. NP is unproven. But I disagree that “most real world problems are not giant knapsack problems”. The Cook-Levin theorem showed that many of the most interesting problems are reducible to NP-complete problems. I’m going to quote this paper by Scott-Aaronson, but it is a great read and I hope you check out the whole thing. https://www.scottaaronson.com/papers/npcomplete.pdf
Even many computer scientists do not seem to appreciate how different the world would be if we could solve NP-complete problems efficiently. I have heard it said, with a straight face, that a proof of P = NP would be important because it would let airlines schedule their flights better, or shipping companies pack more boxes in their trucks! One person who did understand was G ̈odel. In his celebrated 1956 letter to von Neumann (see [69]), in which he first raised the P versus NP question, G ̈odel says that a linear or quadratic-time procedure for what we now call NP-complete problems would have “consequences of the greatest magnitude.” For such an procedure “would clearly indicate that, despite the unsolvability of the Entscheidungsproblem, the mental effort of the mathematician in the case of yes-or-no questions could be completely replaced by machines.”
But it would indicate even more. If such a procedure existed, then we could quickly find the smallest Boolean circuits that output (say) a table of historical stock market data, or the human genome, or the complete works of Shakespeare. It seems entirely conceivable that, by analyzing these circuits, we could make an easy fortune on Wall Street, or retrace evolution, or even generate Shakespeare’s 38th play. For broadly speaking, that which we can compress we can understand, and that which we can understand we can predict. Indeed, in a recent book [12], Eric Baum argues that much of what we call ‘insight’ or ‘intelligence’ simply means finding succinct representations for our sense data. On his view, the human mind is largely a bundle of hacks and heuristics for this succinct-representation problem, cobbled together over a billion years of evolution. So if we could solve the general case—if knowing something was tantamount to knowing the shortest efficient description of it—then we would be almost like gods. The NP Hardness Assumption is the belief that such power will be forever beyond our reach.
I take the NP-hardness assumption as foundational. That being the case, a lot of talk of AI x-risk sounds to me like saying that AI will be an NP oracle. (For example, the idea that a highly intelligent expert system designing tractors could somehow “get out of the box” and threaten humanity, would require a highly accurate predictive model that would almost certainly contain one or many NP-complete subproblems)
But current weather prediction doesn’t use that data. It just uses the weather satellite data, because it isn’t smart enough to make sense of all the social media data. I mean you could argue that most of the good data is from the weather satellite. That social media data doesn’t help much even if you are smart enough to use it. If that is true, that would be a way that the weather problem differs from many other problems.
Yes I would argue that current weather prediction doesn’t use social media data because cameras at optical wavelengths cannot sound the upper atmosphere. Physics means there is no free lunch from social media data.
I would argue that most real world problems are observationally and experimentally bound. The seminal paper on photoelectric effect was a direct consequence of a series of experimental results from the 19th century. Relativity is the same story. It isn’t like there were measurements of the speed of light or the ratio of frequency to energy of photons available in the 17th century just waiting for someone with sufficient intelligence to find them in the 17th century equivalent of social media. And no amount of data on european peasants (the 17th century equivalent of facebook) would be a sufficient substitute. The right data makes all the difference.
A common AI risk problem like manipulating a programmer into escalating AI privileges is a less legible problem than examples from physics but I have no reason to think that it won’t also be observationally bound. Making an attempt to manipulate the programmer and being so accurate in the prediction that the AI is highly confident it won’t be caught would require a model of the programmer as detailed(or more) than an atmospheric model. There is no guarantee the programmer has any psychological vulnerabiliies. There is no guarantee that they share the right information on social media. Even if they’re a prolific poster, why would we think this information is sufficient to manipulate them?
The smallest boolean circuit trick is a reasonable trick, if you can get it to work efficiently. But it won’t magically be omniscient at everything. It would be just one fairly useful tool in the ML toolbox.
“Minimal circuit” based approaches will fail badly when the data comes from a simple to specify but computationally heavy function. For example, the minimal boolean circuit trained to take in a point on the complex plane (with X and Y as IEEE floats) and output if that point is in the mandelbrot set. This algorithm will fail reasonable numbers of training points.
If the 3 sat algorithm is O(n^4) then this algorithm might not be that useful compared to other approaches.
On the other hand, a loglinear algorithm that produced a circuit that was usually almost optimal, that could be useful.
What’s the runtime complexity of rowhammering your own hardware to access the internet? O(1)? Meaningless. Asymptotic runtime complexity is a mathematical tool that assumes an infinite sequence of ever harder problems. (An infinite sequence of ever longer lists to sort, or 3-sat’s to solve) There is not an infinite sequence of ever harder problems in reality. Computational complexity is mostly concerned with the worst case, and finding the absolutely perfect solution. In reality, an AI can use algorithms that find a pretty good solution most of the time.
A common AI risk problem like manipulating a programmer into escalating AI privileges is a less legible problem than examples from physics but I have no reason to think that it won’t also be observationally bound.
Obviously there is a bound based on observation for every problem, just often that bound is crazy high on our scales. For a problem humans understand well, we may be operating close to that bound. For the many problems that are “illegible” or “hard for humans to think about” or “confusing”, we are nowhere near the bound, so the AI has room to beat the pants off us with the same data.
I would argue that most real world problems are observationally and experimentally bound.
And no amount of data on european peasants (the 17th century equivalent of facebook) would be a sufficient substitute.
Consider a world in which humans, being smart but not that smart, can figure out relativity from good clear physics data. Could a superintelligence figure out relativity based on the experiences of the typical caveman? You seem to be arguing that a superintelligence couldn’t manage this because Einstein didn’t. Apparently gold wouldn’t be yellowish if it weren’t for relativistic effects on the innermost electrons. The sun is shining. Life ⇒ Evolution over millions of years. Sun’s energy density too high for chemical fuel. E=mc^2? Why the night sky is dark. Redshift and a universe with a big bang. These clues, and probably more, have been available to most humans throughout history.
These clues weren’t enough to lead Einstein to relativity, but Einstein was only human.
In reality, an AI can use algorithms that find a pretty good solution most of the time.
If you replace “AI” with “ML” I agree with this point. And yep this is what we can do with the networks we’re scaling. But “pretty good most of the time” doesn’t get you an x-risk intelligence. It gets you some really cool tools.
If the 3 sat algorithm is O(n^4) then this algorithm might not be that useful compared to other approaches.
If 3 SAT is O(n^4) then P=NP and back to Aaronson’s point; the fundamental structure of reality is much different than we think it is. (did you mean “4^N”? Plenty of common algorithms are quartic.)
For the many problems that are “illegible” or “hard for humans to think about” or “confusing”, we are nowhere near the bound, so the AI has room to beat the pants off us with the same data.
The assertion that “illegible” means “requiring more intelligence” rather than “ill-posed” or “underspecified” doesn’t seem obvious to me. Maybe you can expand on this?
Could a superintelligence figure out relativity based on the experiences of the typical caveman?..These clues weren’t enough to lead Einstein to relativity, but Einstein was only human.
I’m not sure I can draw the inference that this means it was possible to generate the theory without the key observations it is explaining. What I’m grasping at is how we can bound what cababilities more intelligence gives an agent. It seems intuitive to me that there must be limits and we can look to physics and math to try to understand them. Which leads us here:
Meaningless. Asymptotic runtime complexity is a mathematical tool that assumes an infinite sequence of ever harder problems.
I disagree. We’ve got a highly speculative question in front of us. “What can a machine intelligence greater than ours accomplish”? We can’t really know what it would be like to be twice as smart any more than an ape can. But if we stipulate that the machine is running on Turing Complete hardware and accept NP hardness then we can at least put an upper bound on the capabilities of this machine.
Concretely, I can box the machine using a post-quantum cryptographic standard and know that it lacks the computational resources to break out before the heat death of the universe. More abstractly, any AI risk scenario cannot require solving NP problems of more than modest size. (because of completeness, this means many problems and many of the oft-posed risk scenarios are off the table)
If you replace “AI” with “ML” I agree with this point. And yep this is what we can do with the networks we’re scaling. But “pretty good most of the time” doesn’t get you an x-risk intelligence. It gets you some really cool tools.
On some problems, finding the exact best solution is intractable. On these problems, its all approximations and tricks that usually work. Whether the simplest dumb ML algorithm running with didly squat compute, or some vastly superintelligent AI running on a Matrioska brain.
Take hacking a computer system that controls nukes or something. The problem of finding the fastest way to hack an arbitrary computer system is NP hard. But humans sometimes hack computers without exponentially vast brains. Suppose the AI’s hacking algorithm can hack 99% of all computer systems that are theoretically possible to hack with unlimited compute. And The AI takes at most 10% longer than the theoretically minimum time on those problems.
This AI is still clearly dangerous. Especially if it isn’t just a hacking tool. It has a big picture view of the world and what it wants to achieve.
In short, maybe P!=NP and there is no perfect algoritm, but its possible to be a lot better than current ML, and a lot better than humans, and you don’t need a perfect algorithm to create an X risk.
If 3 SAT is O(n^4) then P=NP and back to Aaronson’s point; the fundamental structure of reality is much different than we think it is. (did you mean “4^N”? Plenty of common algorithms are quartic.)
If 3-sat is O(n^1000,000) then P=NP on a technicality, but the algorithm is totally useless as it is far too slow in practice. If its O(n^4) there are still some uses, but it would seriously hamper the effectiveness of the minimum circuit style predictors. Neural nets are trained on a lot of data. With an O(n^4) algorithm, training beyond 10kb of data will be getting difficult, depending somewhat on the constant.
The assertion that “illegible” means “requiring more intelligence” rather than “ill-posed” or “underspecified” doesn’t seem obvious to me. Maybe you can expand on this?
If you consider the problem of persuading a human to let you out of the box in an AI boxing scenario, well that is perfectly well posed. (There is a big red “open box” button, and either its pressed or it isn’t. ) But we don’t have enough understanding of phycology to do it. Pick some disease we don’t know the cause of or how to cure yet. There will be lots of semi relevant information in biology textbooks. There will be case reports and social media posts and a few confusing clinical trials.
In weather, we know the equations, and there are equations. Any remaining uncertainty is uncertainty about windspeed, temperature etc. But suppose you had a lot of weather data, but hadn’t invented the equations yet. You have a few rules of thumb about how weather patterns move. When you invent the equations, suddenly you can predict so much more.
It seems intuitive to me that there must be limits and we can look to physics and math to try to understand them.
Of course their are bounds. But those bounds are really high on a human scale.
I’m not sure I can draw the inference that this means it was possible to generate the theory without the key observations it is explaining.
I am arguing that there are several facts observable to the average caveman that are explainable by general relativity. Einstein needed data from experiments as well. If you take 10 clues to solve a puzzle, but once you solve it, all the pieces fit beautifully together, that indicates that the problem may have been solvable with fewer clues. It wasn’t that Pythagoras had 10 trillion theories, each as mathematically elegant as general relativity, in mind, and needed experiments to tell which one was true. Arguably Newton had 1 theory like that, and there were still a few clues available that hinted towards relativity.
Concretely, I can box the machine using a post-quantum cryptographic standard and know that it lacks the computational resources to break out before the heat death of the universe. More abstractly, any AI risk scenario cannot require solving NP problems of more than modest size. (because of completeness, this means many problems and many of the oft-posed risk scenarios are off the table)
A large fraction of hacking doesn’t involve breaking cryptographic protocols in the field of cryptographic protocols, but in places where those abstractions break down. Sure you use that post quantum cryptographic standard. But then you get an attack that runs a computation that takes 5 or 30 seconds depending on a single bit of the key, and seeing if the cooling fan turns on. Data on what the cooling fan gets up to wasn’t included in the ideal mathematical model in which the problem was NP hard. Or it could be something as stupid as an easily guessable admin password. Or a cryptographic library calls a big int library. The big int library has a debug mode that logs all the arithmetic done. The debug mode can be turned on with a buffer overflow. So turn on debug and check the logs for the private keys. Most hacks aren’t about breaking NP hard math, but about the surrounding software being buggy or imperfect, allowing you do bypass the math.
The NP-hard maths is about the worst case. I can give you a 3sat of a million variables that is trivial to solve. The maths conjectures that it is hard to solve the worst case. Is hacking a particular computer or designing a bioweapon the worst case of a 3 sat problem, or is it one of the easier cases? I don’t know. Large 3 sat problems are often solved in practice, like a million variable problems are solved in minutes. Because NP hardness is about the worst case. And the practical problem people are solving isn’t the worst case.
More abstractly, any AI risk scenario cannot require solving NP problems of more than modest size. (because of completeness, this means many problems and many of the oft-posed risk scenarios are off the table)
Are you claiming that designing a lethal bioweapon is NP hard? That building nanotech is NP hard? Like using hacking and social engineering to start a nuclear war is NP hard? What are these large 3 sat problems that must be solved before the world can be destroyed?
P vs. NP is unproven. But I disagree that “most real world problems are not giant knapsack problems”. The Cook-Levin theorem showed that many of the most interesting problems are reducible to NP-complete problems. I’m going to quote this paper by Scott-Aaronson, but it is a great read and I hope you check out the whole thing. https://www.scottaaronson.com/papers/npcomplete.pdf
I take the NP-hardness assumption as foundational. That being the case, a lot of talk of AI x-risk sounds to me like saying that AI will be an NP oracle. (For example, the idea that a highly intelligent expert system designing tractors could somehow “get out of the box” and threaten humanity, would require a highly accurate predictive model that would almost certainly contain one or many NP-complete subproblems)
Yes I would argue that current weather prediction doesn’t use social media data because cameras at optical wavelengths cannot sound the upper atmosphere. Physics means there is no free lunch from social media data.
I would argue that most real world problems are observationally and experimentally bound. The seminal paper on photoelectric effect was a direct consequence of a series of experimental results from the 19th century. Relativity is the same story. It isn’t like there were measurements of the speed of light or the ratio of frequency to energy of photons available in the 17th century just waiting for someone with sufficient intelligence to find them in the 17th century equivalent of social media. And no amount of data on european peasants (the 17th century equivalent of facebook) would be a sufficient substitute. The right data makes all the difference.
A common AI risk problem like manipulating a programmer into escalating AI privileges is a less legible problem than examples from physics but I have no reason to think that it won’t also be observationally bound. Making an attempt to manipulate the programmer and being so accurate in the prediction that the AI is highly confident it won’t be caught would require a model of the programmer as detailed(or more) than an atmospheric model. There is no guarantee the programmer has any psychological vulnerabiliies. There is no guarantee that they share the right information on social media. Even if they’re a prolific poster, why would we think this information is sufficient to manipulate them?
The smallest boolean circuit trick is a reasonable trick, if you can get it to work efficiently. But it won’t magically be omniscient at everything. It would be just one fairly useful tool in the ML toolbox.
“Minimal circuit” based approaches will fail badly when the data comes from a simple to specify but computationally heavy function. For example, the minimal boolean circuit trained to take in a point on the complex plane (with X and Y as IEEE floats) and output if that point is in the mandelbrot set. This algorithm will fail reasonable numbers of training points.
If the 3 sat algorithm is O(n^4) then this algorithm might not be that useful compared to other approaches.
On the other hand, a loglinear algorithm that produced a circuit that was usually almost optimal, that could be useful.
What’s the runtime complexity of rowhammering your own hardware to access the internet? O(1)? Meaningless. Asymptotic runtime complexity is a mathematical tool that assumes an infinite sequence of ever harder problems. (An infinite sequence of ever longer lists to sort, or 3-sat’s to solve) There is not an infinite sequence of ever harder problems in reality. Computational complexity is mostly concerned with the worst case, and finding the absolutely perfect solution. In reality, an AI can use algorithms that find a pretty good solution most of the time.
Obviously there is a bound based on observation for every problem, just often that bound is crazy high on our scales. For a problem humans understand well, we may be operating close to that bound. For the many problems that are “illegible” or “hard for humans to think about” or “confusing”, we are nowhere near the bound, so the AI has room to beat the pants off us with the same data.
Consider a world in which humans, being smart but not that smart, can figure out relativity from good clear physics data. Could a superintelligence figure out relativity based on the experiences of the typical caveman? You seem to be arguing that a superintelligence couldn’t manage this because Einstein didn’t. Apparently gold wouldn’t be yellowish if it weren’t for relativistic effects on the innermost electrons. The sun is shining. Life ⇒ Evolution over millions of years. Sun’s energy density too high for chemical fuel. E=mc^2? Why the night sky is dark. Redshift and a universe with a big bang. These clues, and probably more, have been available to most humans throughout history.
These clues weren’t enough to lead Einstein to relativity, but Einstein was only human.
If you replace “AI” with “ML” I agree with this point. And yep this is what we can do with the networks we’re scaling. But “pretty good most of the time” doesn’t get you an x-risk intelligence. It gets you some really cool tools.
If 3 SAT is O(n^4) then P=NP and back to Aaronson’s point; the fundamental structure of reality is much different than we think it is. (did you mean “4^N”? Plenty of common algorithms are quartic.)
The assertion that “illegible” means “requiring more intelligence” rather than “ill-posed” or “underspecified” doesn’t seem obvious to me. Maybe you can expand on this?
I’m not sure I can draw the inference that this means it was possible to generate the theory without the key observations it is explaining. What I’m grasping at is how we can bound what cababilities more intelligence gives an agent. It seems intuitive to me that there must be limits and we can look to physics and math to try to understand them. Which leads us here:
I disagree. We’ve got a highly speculative question in front of us. “What can a machine intelligence greater than ours accomplish”? We can’t really know what it would be like to be twice as smart any more than an ape can. But if we stipulate that the machine is running on Turing Complete hardware and accept NP hardness then we can at least put an upper bound on the capabilities of this machine.
Concretely, I can box the machine using a post-quantum cryptographic standard and know that it lacks the computational resources to break out before the heat death of the universe. More abstractly, any AI risk scenario cannot require solving NP problems of more than modest size. (because of completeness, this means many problems and many of the oft-posed risk scenarios are off the table)
On some problems, finding the exact best solution is intractable. On these problems, its all approximations and tricks that usually work. Whether the simplest dumb ML algorithm running with didly squat compute, or some vastly superintelligent AI running on a Matrioska brain.
Take hacking a computer system that controls nukes or something. The problem of finding the fastest way to hack an arbitrary computer system is NP hard. But humans sometimes hack computers without exponentially vast brains. Suppose the AI’s hacking algorithm can hack 99% of all computer systems that are theoretically possible to hack with unlimited compute. And The AI takes at most 10% longer than the theoretically minimum time on those problems.
This AI is still clearly dangerous. Especially if it isn’t just a hacking tool. It has a big picture view of the world and what it wants to achieve.
In short, maybe P!=NP and there is no perfect algoritm, but its possible to be a lot better than current ML, and a lot better than humans, and you don’t need a perfect algorithm to create an X risk.
If 3-sat is O(n^1000,000) then P=NP on a technicality, but the algorithm is totally useless as it is far too slow in practice. If its O(n^4) there are still some uses, but it would seriously hamper the effectiveness of the minimum circuit style predictors. Neural nets are trained on a lot of data. With an O(n^4) algorithm, training beyond 10kb of data will be getting difficult, depending somewhat on the constant.
If you consider the problem of persuading a human to let you out of the box in an AI boxing scenario, well that is perfectly well posed. (There is a big red “open box” button, and either its pressed or it isn’t. ) But we don’t have enough understanding of phycology to do it. Pick some disease we don’t know the cause of or how to cure yet. There will be lots of semi relevant information in biology textbooks. There will be case reports and social media posts and a few confusing clinical trials.
In weather, we know the equations, and there are equations. Any remaining uncertainty is uncertainty about windspeed, temperature etc. But suppose you had a lot of weather data, but hadn’t invented the equations yet. You have a few rules of thumb about how weather patterns move. When you invent the equations, suddenly you can predict so much more.
Of course their are bounds. But those bounds are really high on a human scale.
I am arguing that there are several facts observable to the average caveman that are explainable by general relativity. Einstein needed data from experiments as well. If you take 10 clues to solve a puzzle, but once you solve it, all the pieces fit beautifully together, that indicates that the problem may have been solvable with fewer clues. It wasn’t that Pythagoras had 10 trillion theories, each as mathematically elegant as general relativity, in mind, and needed experiments to tell which one was true. Arguably Newton had 1 theory like that, and there were still a few clues available that hinted towards relativity.
A large fraction of hacking doesn’t involve breaking cryptographic protocols in the field of cryptographic protocols, but in places where those abstractions break down. Sure you use that post quantum cryptographic standard. But then you get an attack that runs a computation that takes 5 or 30 seconds depending on a single bit of the key, and seeing if the cooling fan turns on. Data on what the cooling fan gets up to wasn’t included in the ideal mathematical model in which the problem was NP hard. Or it could be something as stupid as an easily guessable admin password. Or a cryptographic library calls a big int library. The big int library has a debug mode that logs all the arithmetic done. The debug mode can be turned on with a buffer overflow. So turn on debug and check the logs for the private keys. Most hacks aren’t about breaking NP hard math, but about the surrounding software being buggy or imperfect, allowing you do bypass the math.
The NP-hard maths is about the worst case. I can give you a 3sat of a million variables that is trivial to solve. The maths conjectures that it is hard to solve the worst case. Is hacking a particular computer or designing a bioweapon the worst case of a 3 sat problem, or is it one of the easier cases? I don’t know. Large 3 sat problems are often solved in practice, like a million variable problems are solved in minutes. Because NP hardness is about the worst case. And the practical problem people are solving isn’t the worst case.
Are you claiming that designing a lethal bioweapon is NP hard? That building nanotech is NP hard? Like using hacking and social engineering to start a nuclear war is NP hard? What are these large 3 sat problems that must be solved before the world can be destroyed?