Nothing to do with it at all? I’m curious as to how you reach that conclusion.
P = NP is effectively indistinguishable from P = ALL. Like PaulFChristiano said, If P = NP (in a practical way), then FOOMs are a dime a dozen.
No. There are many fairly natural problems which are not in P. For example, given a specific Go position does white or black have a win? This is in EXP
The difficulty of FOOMing for most entities such as humans even given practical P=NP is still severe. See my discussion with Paul.
And assuming P != NP, the fact that NP-complete problems aren’t efficiently solvable in the general case doesn’t mean paperclipping the universe is the least bit difficult.
I’m puzzled at how you can reach such a conclusion. Many natural problems that an entity trying to FOOM would want to do are NP complete. For example, graph coloring comes up in memory optimization and traveling salesman comes up in circuit design. Now, in a prior conversation I had with Cousin It he made the excellent point that a FOOMing AI might not need to actually deal with worst case instances of these problems. But that is a more subtle issue than what you seem to be claiming.
I’m confused or about to display my ignorance. When you write:
There are many fairly natural problems which are not in P. For example, given a specific Go position does white or black have a win? This is in EXP
Are you saying that evaluating a Go position has exponential (time?) cost even on a nondeterministic machine? I thought that any given string of moves to the end of the game could be evaluated in polynomial (N^2?) time. I thought that the full set of possible strings of moves could be evaluated (naively) in exponential time on a deterministic machine and polynomial time on a nondeterministic machine—so I thought Go position evaluation would be in NP. I think you are saying that it is more costly than that. Are you saying that, and what am I getting wrong?
“Does this position win?” has a structure like “Is there a move such that, for each possible reply there is a move such that, for each possible reply… you win.”—where existential and universal quantifiers alternate in the nesting. In a SAT problem on the other hand you just have a nest of existentials. I don’t know about Go specifically, but that’s my understanding of the usual core difference between games and SAT.
Much appreciated! So the NP solution to SAT is basically an OR over all of the possible assignments of the variables, where here (or for alternating move games in general), we’ve got alternating ORs and ANDs on sequential moves.
I’m not sure what you are getting wrong. My initial inclination was to think as you do. But then I thought of this:
You are probably imagining N to be the number of moves deep that need to be searched. Which you probably think is roughly the square of the board size (nominally, 19). The trouble is, what N really means is the size of the specific problem instance. So, it is possible to imagine Go problems on 1001x1001 boards where the number of stones already played is small. I.e. N is much less than a million, but the amount of computation needed to search the tree is on the order of 1000000^1000000.
ETA: This explanation is wrong. Darius got it right.
Much appreciated! I was taking N to be the number of squares on the board. My current thought is that, as you said, the number of possible move sequences on an N square board is of the order of N^N (actually, I think slightly smaller: N!). As you said, N may be much larger than the number of stones already played.
My current understanding is that board size if fixed for any given Go problem. Is that true or false? If it is true, then I’d think that the factor of N branching at each step in the tree of moves is just what gets swept into the nondeterministic part of NP.
There are many fairly natural problems which are not in P. For example, given a specific Go position does white or black have a win? This is in EXP
Are you saying that evaluating a Go position has exponential (time?) cost even on a nondeterministic machine?
If one assumes everything that is conjectured, then yes. To say that it is EXP-hard is to say that it takes exponential time on a deterministic machine. This does not immediately say how much time it takes on a non-deterministic machine. It is not ruled out that NP=EXP, but it is extremely implausible. Also doubted, though more plausible, is that PSPACE=EXP. PSPACE doesn’t care about determinism.
I’m not completely sure what you mean. Darius’s response seems relevant (in particular, you may want to look at the difference between a general non-deterministic Turing machine and an alternating Turing machine). However, there seems to be possibly another issue here: When mathematicians and computer scientists discuss polynomial time, they are talking about polynomials of the length of the input, not polynomials of the input (similarly, for exponential time and other classes). Thus, for example, to say that PRIMES is in P we mean that there’s an algorithm that answers whether a given integer is prime that is time bounded by a polynomial of log_2 p (assuming p is written in base 2).
There are indeed natural problems outside of NP, but an AI will be able to quickly answer any such queries in a way that, to a lesser intelligence, looks indistinguishable from an oracle’s answers.
There are indeed natural problems outside of NP, but an AI will be able to quickly answer any such queries in a way that, to a lesser intelligence, looks indistinguishable from an oracle’s answers.
How do you know that? What makes you reach that conclusion?
Do you mean an AI that has already FOOMed? If so, this is sort of a trivial claim.
If you are talking about a pre-FOOM AI then I don’t see why you think this is such an obvious conclusion. And the issue at hand is precisely what the AI could do leading up to and during FOOM.
Determining whether white or black wins at GO is certainly not in P (in fact certainly not in NP, I think, if the game can be exponentially long), but in the real world you don’t care whether white or black wins. You care about whether you win in the particular game of Go you are playing, which is in NP (although with bad constants, since you have to simulate whoever you are playing against).
There is a compelling argument to be made that any problem you care about is in NP, although in general the constants will be impractical in the same sense that building a computer to simulate the universe is impractical, even if the problem is in P. In fact, this question doesn’t really matter, because P is not actually the class of problems which can be solved in practice. It is a convenient approximation which allows us to state some theorems we have a chance of proving in the next century.
I think the existence of computational lower bounds is clearly of extreme importance to anything clever enough to discover optimal algorithms (and probably also to humans in the very long term for similar reasons). P != NP is basically the crudest such question, and even though I am fairly certain I know which way that question goes the probability of an AI fooming depends on much subtler problems which I can’t even begin to understand. In fact, basically the only reason I personally am interested in the P vs NP question is because I think it involves techniques which will eventually help us address these more difficult problems.
Determining whether white or black wins at GO is certainly not in P (in fact certainly not in NP, I think, if the game can be exponentially long), but in the real world you don’t care whether white or black wins. You care about whether you win in the particular game of Go you are playing, which is in NP (although with bad constants, since you have to simulate whoever you are playing against).
Huh? I don’t follow this at all. The question of any fixed game who would win is trivially in NP because it is doable in constant time. Any single question is always answerable in constant time. Am I misunderstanding you?
Suppose I want to choose how to behave to achieve some goal. Either what genes to put in a cell I am growing or what moves to play in a game of go or etc. Presumably I can determine whether any fixed prescription will cause me to attain my goal—I can simulate the universe and check the outcome at the end. Thus checking whether a particular sequence of actions (or a particular design, strategy, etc.) has the desired property is in P. Thus finding one with the desired property is in NP. The same applies to determining how to build a cell with desired properties, or how to beat the world’s best go player, etc. None of this is to say that P = NP sheds light on how easy these questions actually are, but P = NP is the normal theoretical interpretation, and in fact the only theoretical interpretation that makes sense if you are going to stick with the position that P is precisely the class of problems that an AI can solve.
I’m having some trouble parsing what you have wrote.
Presumably I can determine whether any fixed prescription will cause me to attain my goal—I can simulate the universe and check the outcome at the end. Thus checking whether a particular sequence of actions (or a particular design, strategy, etc.) has the desired property is in P.
I don’t follow this line of reasoning at all. Whether a problem is in P is a statement about the length of time it takes in general to solve instances. Also, a problem for this purpose is a collection of questions of the form “for given input N, does N have property A?”
None of this is to say that P = NP sheds light on how easy these questions actually are, but P = NP is the normal theoretical interpretation, and in fact the only theoretical interpretation that makes sense if you are going to stick with the position that P is precisely the class of problems that an AI can solve.
I’m not sure what you mean by this. First of all, the general consensus is that P !=NP. Second of all, in no interpretation is P is somehow precisely the set of problems that an AI can solve. It seems you are failing to distinguish between instances of problems and the general problems. Thus for example, the traveling salesman problem is NP complete. Even if P != NP, I can still solve individual traveling salesman problems (you can probably solve any instance with fewer than five nodes more or less by hand without too much effort.). Similarly, even if factoring turns out to be not in P, it doesn’t mean anyone is going to have trouble factoring 15.
Nothing to do with it at all? I’m curious as to how you reach that conclusion.
No. There are many fairly natural problems which are not in P. For example, given a specific Go position does white or black have a win? This is in EXP
The difficulty of FOOMing for most entities such as humans even given practical P=NP is still severe. See my discussion with Paul.
I’m puzzled at how you can reach such a conclusion. Many natural problems that an entity trying to FOOM would want to do are NP complete. For example, graph coloring comes up in memory optimization and traveling salesman comes up in circuit design. Now, in a prior conversation I had with Cousin It he made the excellent point that a FOOMing AI might not need to actually deal with worst case instances of these problems. But that is a more subtle issue than what you seem to be claiming.
I’m confused or about to display my ignorance. When you write:
Are you saying that evaluating a Go position has exponential (time?) cost even on a nondeterministic machine? I thought that any given string of moves to the end of the game could be evaluated in polynomial (N^2?) time. I thought that the full set of possible strings of moves could be evaluated (naively) in exponential time on a deterministic machine and polynomial time on a nondeterministic machine—so I thought Go position evaluation would be in NP. I think you are saying that it is more costly than that. Are you saying that, and what am I getting wrong?
“Does this position win?” has a structure like “Is there a move such that, for each possible reply there is a move such that, for each possible reply… you win.”—where existential and universal quantifiers alternate in the nesting. In a SAT problem on the other hand you just have a nest of existentials. I don’t know about Go specifically, but that’s my understanding of the usual core difference between games and SAT.
Much appreciated! So the NP solution to SAT is basically an OR over all of the possible assignments of the variables, where here (or for alternating move games in general), we’ve got alternating ORs and ANDs on sequential moves.
I’m not sure what you are getting wrong. My initial inclination was to think as you do. But then I thought of this:
You are probably imagining N to be the number of moves deep that need to be searched. Which you probably think is roughly the square of the board size (nominally, 19). The trouble is, what N really means is the size of the specific problem instance. So, it is possible to imagine Go problems on 1001x1001 boards where the number of stones already played is small. I.e. N is much less than a million, but the amount of computation needed to search the tree is on the order of 1000000^1000000.
ETA: This explanation is wrong. Darius got it right.
Much appreciated! I was taking N to be the number of squares on the board. My current thought is that, as you said, the number of possible move sequences on an N square board is of the order of N^N (actually, I think slightly smaller: N!). As you said, N may be much larger than the number of stones already played.
My current understanding is that board size if fixed for any given Go problem. Is that true or false? If it is true, then I’d think that the factor of N branching at each step in the tree of moves is just what gets swept into the nondeterministic part of NP.
If one assumes everything that is conjectured, then yes. To say that it is EXP-hard is to say that it takes exponential time on a deterministic machine. This does not immediately say how much time it takes on a non-deterministic machine. It is not ruled out that NP=EXP, but it is extremely implausible. Also doubted, though more plausible, is that PSPACE=EXP. PSPACE doesn’t care about determinism.
I’m not completely sure what you mean. Darius’s response seems relevant (in particular, you may want to look at the difference between a general non-deterministic Turing machine and an alternating Turing machine). However, there seems to be possibly another issue here: When mathematicians and computer scientists discuss polynomial time, they are talking about polynomials of the length of the input, not polynomials of the input (similarly, for exponential time and other classes). Thus, for example, to say that PRIMES is in P we mean that there’s an algorithm that answers whether a given integer is prime that is time bounded by a polynomial of log_2 p (assuming p is written in base 2).
There are indeed natural problems outside of NP, but an AI will be able to quickly answer any such queries in a way that, to a lesser intelligence, looks indistinguishable from an oracle’s answers.
How do you know that? What makes you reach that conclusion?
Do you mean an AI that has already FOOMed? If so, this is sort of a trivial claim.
If you are talking about a pre-FOOM AI then I don’t see why you think this is such an obvious conclusion. And the issue at hand is precisely what the AI could do leading up to and during FOOM.
Determining whether white or black wins at GO is certainly not in P (in fact certainly not in NP, I think, if the game can be exponentially long), but in the real world you don’t care whether white or black wins. You care about whether you win in the particular game of Go you are playing, which is in NP (although with bad constants, since you have to simulate whoever you are playing against).
There is a compelling argument to be made that any problem you care about is in NP, although in general the constants will be impractical in the same sense that building a computer to simulate the universe is impractical, even if the problem is in P. In fact, this question doesn’t really matter, because P is not actually the class of problems which can be solved in practice. It is a convenient approximation which allows us to state some theorems we have a chance of proving in the next century.
I think the existence of computational lower bounds is clearly of extreme importance to anything clever enough to discover optimal algorithms (and probably also to humans in the very long term for similar reasons). P != NP is basically the crudest such question, and even though I am fairly certain I know which way that question goes the probability of an AI fooming depends on much subtler problems which I can’t even begin to understand. In fact, basically the only reason I personally am interested in the P vs NP question is because I think it involves techniques which will eventually help us address these more difficult problems.
Huh? I don’t follow this at all. The question of any fixed game who would win is trivially in NP because it is doable in constant time. Any single question is always answerable in constant time. Am I misunderstanding you?
Suppose I want to choose how to behave to achieve some goal. Either what genes to put in a cell I am growing or what moves to play in a game of go or etc. Presumably I can determine whether any fixed prescription will cause me to attain my goal—I can simulate the universe and check the outcome at the end. Thus checking whether a particular sequence of actions (or a particular design, strategy, etc.) has the desired property is in P. Thus finding one with the desired property is in NP. The same applies to determining how to build a cell with desired properties, or how to beat the world’s best go player, etc. None of this is to say that P = NP sheds light on how easy these questions actually are, but P = NP is the normal theoretical interpretation, and in fact the only theoretical interpretation that makes sense if you are going to stick with the position that P is precisely the class of problems that an AI can solve.
I’m having some trouble parsing what you have wrote.
I don’t follow this line of reasoning at all. Whether a problem is in P is a statement about the length of time it takes in general to solve instances. Also, a problem for this purpose is a collection of questions of the form “for given input N, does N have property A?”
I’m not sure what you mean by this. First of all, the general consensus is that P !=NP. Second of all, in no interpretation is P is somehow precisely the set of problems that an AI can solve. It seems you are failing to distinguish between instances of problems and the general problems. Thus for example, the traveling salesman problem is NP complete. Even if P != NP, I can still solve individual traveling salesman problems (you can probably solve any instance with fewer than five nodes more or less by hand without too much effort.). Similarly, even if factoring turns out to be not in P, it doesn’t mean anyone is going to have trouble factoring 15.