![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Entry tags:
December days: P vs. NP
On our date a couple of weeks ago, I found myself explaining to ![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
ghoti the basics of why P vs. NP is an interesting question. (Clearly, we have the best romantic conversations.) I'd like to explain this at a bit more length and to more people. You'll have to care at least a little bit about maths to find this interesting, but I hope I've managed to explain it clearly enough that it doesn't require any specialist knowledge. Note that I'm not actually a complexity researcher, just an interested person with some relevant background.
Complexity theory
Complexity theory was one of the bits of the crossover between maths and computer science that I always loved, ever since encountering a pop-science version of it in my teens. It deals with the question of working out how fast it's possible to solve particular classes of problems. Normally, the way you express this is by considering how quickly the time required to solve the problem grows as the problem itself gets larger. You discard all the constant factors and lower-order terms because those are boring to calculate and become insignificant as the problem grows anyway: so you might talk about an inefficient sorting algorithm on n items being O(n^2), because the upper bound on its running time grows at the rate of n-squared. If you have two procedures, one of which takes 100*n+1000 time to run, and the other of which takes n^2, the former will ultimately be faster for big enough problems even if the latter is faster for some simple cases, so we normally consider the former as being "better". In practice you don't normally get particularly large constant factors and the "big-O" time is indeed what dominates.
Viewed like this, there's a hierarchy of problems in terms of their difficulty. The ones that are upper-bounded by n to the power of something are referred to as "polynomial-time algorithms", or P for short. Anything whose running time is upper-bounded by something like 2^n ultimately grows faster than any polynomial, and is referred to as an "exponential-time algorithm". You can get worse still, 2^(2^n) and so forth (super-exponential), though fortunately these rarely show up in real-world problems. You can certainly get pathologically terrible polynomial-time algorithms, O(n^1000) or whatever, but in practice anything in P tends to be more or less feasible to compute, and anything that's exponential-time or worse tends to be infeasible to compute.
(Separately but relatedly, there's the notion of computability or decidability: there are problems that can be stated rigorously but where you can prove that no algorithm can exist to solve them. Most famously, there's the halting problem: given a program and its input, will it ever terminate? You can prove that this is undecidable by hypothesising a program that solves the problem, putting a little wrapper around it that says "if the input program terminates, enter an infinite loop; otherwise, exit immediately", and then running that program with itself as its input: logically it must both terminate and run forever, and thus the hypothetical solution to the halting problem cannot exist. Even if you had an oracle that solved the halting problem, there are still harder problems that you couldn't solve, and indeed there is an infinite hierarchy of undecidability in these terms.)
Now, there are a lot of interesting problems where you can easily (in polynomial time) verify a solution if you're given one, but coming up with a solution is hard. For instance, even though factorisation isn't known to be easy, you can quite easily verify a proposed factorisation of a large integer by multiplying the suggested factors together. You can view this a different way: you could have a polynomial-time solution if you had an algorithm with a decision tree one of whose leaves was the solution, and you had an oracle that determined which choice to make at each step. These problems are called "non-deterministic polynomial-time", or NP. A great deal of research has gone into these problems, and we can make a lot of general statements about them. For instance, we know that there's a class of problems in NP which, if you could solve any one of them in polynomial time, you could also transform that solution into a solution for any other problem in NP using only polynomially more time: these problems are called NP-complete. A famous example is the travelling salesman problem: a salesperson has a list of cities to sell their wares in, and wants to do so with the least possible travel; what is the shortest route that visits each city exactly once and returns to the starting point?
Clearly (mathematician-speak for "I can't be bothered to write out the proof", but hopefully it is actually clear in this case), any problem in P is also in NP. But the question immediately arises: what about the converse? There are lots of problems in NP where we don't know of polynomial solutions, but that doesn't mean they don't exist, and in fact despite very considerable effort nobody has been able to prove this. This has been an open question in theoretical computer science since 1971 when the concept of NP-completeness was introduced, and there's a US $1 million prize for anyone who proves the matter either way. Most complexity researchers think that P probably ≠ NP, but the question has proven itself to be astonishingly difficult to resolve despite a large amount of collective brainpower having gone into it over the years.
This is certainly a question of considerable practical importance and not just an ivory-tower exercise. For instance, problems that are thought not to lie in P (the class of problems that are easy to solve directly) but that are in NP (the class of problems where it's easy to verify a solution) form the heart of strong cryptography: nobody knows how to factorise integers in polynomial time, even though there are algorithms that get very very close to that. So what's taking researchers so long?
Barriers
The P vs. NP problem is one of those that's sufficiently easy to state and understand that a lot of people have a go at it, but in fact well-trodden enough that it's very difficult to break new ground in reality; this means that it's not at all uncommon to run across well-meaning papers that purport to solve it but in fact fail in some way. It's thus quite helpful that one of the areas where complexity theorists have been able to make progress in this area is in proving that a number of strategies are insufficient to distinguish between P and NP, thereby making it much easier to filter out obviously unworkable proposals. (Compare the proof that no non-constant polynomial function of integers can generate only prime numbers, for instance; number theory is another field that's often covered in popular maths and that tends to attract people looking for patterns.)
Relativisation: Imagine a fantasy world where your machine got to use an oracle for free, or at least in polynomial time: a machine that can produce the solution to any problem in a suitable formal language. By definition, such a machine can quickly answer any problem in NP, but that's not the point here: the point is that most (though not all) proofs about complexity theory also apply just the same way if you augment the abstract machines that they're talking about with the ability to contact such an oracle. However, it has been proven that P=NP with respect to some oracles but P≠NP with respect to others; roughly, perhaps, because if the oracle is powerful enough then non-determinism doesn't help, but if the oracle is too weak then it isn't good enough to reach the power of non-determinism. This means that the P vs. NP problem is independent of oracle relativisation, so any proof needs to employ techniques that exploit properties of computation that are specific to the real world and don't work when oracles are involved. This rules out an assortment of techniques such as diagonalisation. (I don't have a direct link for the original paper here, but it's Baker, Gill, and Solovay, "Relativizations of the P ≟ NP question", December 1975.)
As a side note, oracles aren't entirely just a fictional object constructed by theoreticians. Some exist in reality due to quantum computing, such as Shor's algorithm; quantum computers lie outside the model of computation where P and NP are defined, although there are analogous complexity classes in the quantum world.
Over the next decade or two, researchers turned to a different approach, that of expressing algorithms as Boolean circuits and proving lower bounds on their complexity. But in 1993, it was proven that any proof along these lines must either rely on something very specialised about the algorithm in question that isn't broad enough to cover NP, or must involve defining some "non-constructive" property that is outside the realm of most of our mathematical experience. If any natural proof such as this could separate P and NP, then it would also violate a widely-believed but unproven conjecture about pseudo-random generators which would in turn allow us to find a fast way to do things like inverting one-way functions; this would be self-defeating, because it would mean that a natural proof showing that "hard" problems definitely involve slower algorithms than "easy" problems would also automatically produce a fast algorithm to solve a "hard" problem!
The next technique was arithmetisation, which effectively takes the Boolean field and embeds it into something larger so that it's possible to exploit more structure and correct some errors; this technique doesn't relativise, and there's another technique called diagonalisation (similar to that used by Georg Cantor to prove that the real numbers can't be put into a one-to-one correspondence with the natural numbers) which can be combined with it to evade both of the previous barriers. Unfortunately it turns out that even this isn't good enough: there's an additional barrier known as algebrisation, which is an extension of the previous notion of oracles to larger fields, and any proof relying on that is also unable to distinguish P from NP.
What now?
All it would take to demonstrate that P=NP would be just one polynomial-time algorithm for a problem known to be NP-complete, which includes problems that certainly have a great deal of practical applicability and so there's no shortage of incentive to find something. Lower bounds are harder to prove, and proving P≠NP would need to overcome the obstacles above and encode some very deep properties of computation. So it's not necessarily surprising that we don't have a proof yet, but also decent grounds for believing that P≠NP is the more likely answer.
P vs. NP is in fact a very deep question about the nature of mathematical thought. There's a beautiful version of the argument that runs something like this. Mathematical proofs are themselves computational objects if written with sufficient rigour; both theorem-proving software and proof checkers exist; and we know from general experience that it's easier to verify a proof than to create one, which is the essence of the distinction between P and NP. It may in fact be that the very reason it is hard to prove that P≠NP is because P≠NP.
This post is part of my December days series. Please prompt me!
ghoti the basics of why P vs. NP is an interesting question. (Clearly, we have the best romantic conversations.) I'd like to explain this at a bit more length and to more people. You'll have to care at least a little bit about maths to find this interesting, but I hope I've managed to explain it clearly enough that it doesn't require any specialist knowledge. Note that I'm not actually a complexity researcher, just an interested person with some relevant background.Complexity theory
Complexity theory was one of the bits of the crossover between maths and computer science that I always loved, ever since encountering a pop-science version of it in my teens. It deals with the question of working out how fast it's possible to solve particular classes of problems. Normally, the way you express this is by considering how quickly the time required to solve the problem grows as the problem itself gets larger. You discard all the constant factors and lower-order terms because those are boring to calculate and become insignificant as the problem grows anyway: so you might talk about an inefficient sorting algorithm on n items being O(n^2), because the upper bound on its running time grows at the rate of n-squared. If you have two procedures, one of which takes 100*n+1000 time to run, and the other of which takes n^2, the former will ultimately be faster for big enough problems even if the latter is faster for some simple cases, so we normally consider the former as being "better". In practice you don't normally get particularly large constant factors and the "big-O" time is indeed what dominates.
Viewed like this, there's a hierarchy of problems in terms of their difficulty. The ones that are upper-bounded by n to the power of something are referred to as "polynomial-time algorithms", or P for short. Anything whose running time is upper-bounded by something like 2^n ultimately grows faster than any polynomial, and is referred to as an "exponential-time algorithm". You can get worse still, 2^(2^n) and so forth (super-exponential), though fortunately these rarely show up in real-world problems. You can certainly get pathologically terrible polynomial-time algorithms, O(n^1000) or whatever, but in practice anything in P tends to be more or less feasible to compute, and anything that's exponential-time or worse tends to be infeasible to compute.
(Separately but relatedly, there's the notion of computability or decidability: there are problems that can be stated rigorously but where you can prove that no algorithm can exist to solve them. Most famously, there's the halting problem: given a program and its input, will it ever terminate? You can prove that this is undecidable by hypothesising a program that solves the problem, putting a little wrapper around it that says "if the input program terminates, enter an infinite loop; otherwise, exit immediately", and then running that program with itself as its input: logically it must both terminate and run forever, and thus the hypothetical solution to the halting problem cannot exist. Even if you had an oracle that solved the halting problem, there are still harder problems that you couldn't solve, and indeed there is an infinite hierarchy of undecidability in these terms.)
Now, there are a lot of interesting problems where you can easily (in polynomial time) verify a solution if you're given one, but coming up with a solution is hard. For instance, even though factorisation isn't known to be easy, you can quite easily verify a proposed factorisation of a large integer by multiplying the suggested factors together. You can view this a different way: you could have a polynomial-time solution if you had an algorithm with a decision tree one of whose leaves was the solution, and you had an oracle that determined which choice to make at each step. These problems are called "non-deterministic polynomial-time", or NP. A great deal of research has gone into these problems, and we can make a lot of general statements about them. For instance, we know that there's a class of problems in NP which, if you could solve any one of them in polynomial time, you could also transform that solution into a solution for any other problem in NP using only polynomially more time: these problems are called NP-complete. A famous example is the travelling salesman problem: a salesperson has a list of cities to sell their wares in, and wants to do so with the least possible travel; what is the shortest route that visits each city exactly once and returns to the starting point?
Clearly (mathematician-speak for "I can't be bothered to write out the proof", but hopefully it is actually clear in this case), any problem in P is also in NP. But the question immediately arises: what about the converse? There are lots of problems in NP where we don't know of polynomial solutions, but that doesn't mean they don't exist, and in fact despite very considerable effort nobody has been able to prove this. This has been an open question in theoretical computer science since 1971 when the concept of NP-completeness was introduced, and there's a US $1 million prize for anyone who proves the matter either way. Most complexity researchers think that P probably ≠ NP, but the question has proven itself to be astonishingly difficult to resolve despite a large amount of collective brainpower having gone into it over the years.
This is certainly a question of considerable practical importance and not just an ivory-tower exercise. For instance, problems that are thought not to lie in P (the class of problems that are easy to solve directly) but that are in NP (the class of problems where it's easy to verify a solution) form the heart of strong cryptography: nobody knows how to factorise integers in polynomial time, even though there are algorithms that get very very close to that. So what's taking researchers so long?
Barriers
The P vs. NP problem is one of those that's sufficiently easy to state and understand that a lot of people have a go at it, but in fact well-trodden enough that it's very difficult to break new ground in reality; this means that it's not at all uncommon to run across well-meaning papers that purport to solve it but in fact fail in some way. It's thus quite helpful that one of the areas where complexity theorists have been able to make progress in this area is in proving that a number of strategies are insufficient to distinguish between P and NP, thereby making it much easier to filter out obviously unworkable proposals. (Compare the proof that no non-constant polynomial function of integers can generate only prime numbers, for instance; number theory is another field that's often covered in popular maths and that tends to attract people looking for patterns.)
Relativisation: Imagine a fantasy world where your machine got to use an oracle for free, or at least in polynomial time: a machine that can produce the solution to any problem in a suitable formal language. By definition, such a machine can quickly answer any problem in NP, but that's not the point here: the point is that most (though not all) proofs about complexity theory also apply just the same way if you augment the abstract machines that they're talking about with the ability to contact such an oracle. However, it has been proven that P=NP with respect to some oracles but P≠NP with respect to others; roughly, perhaps, because if the oracle is powerful enough then non-determinism doesn't help, but if the oracle is too weak then it isn't good enough to reach the power of non-determinism. This means that the P vs. NP problem is independent of oracle relativisation, so any proof needs to employ techniques that exploit properties of computation that are specific to the real world and don't work when oracles are involved. This rules out an assortment of techniques such as diagonalisation. (I don't have a direct link for the original paper here, but it's Baker, Gill, and Solovay, "Relativizations of the P ≟ NP question", December 1975.)
As a side note, oracles aren't entirely just a fictional object constructed by theoreticians. Some exist in reality due to quantum computing, such as Shor's algorithm; quantum computers lie outside the model of computation where P and NP are defined, although there are analogous complexity classes in the quantum world.
Over the next decade or two, researchers turned to a different approach, that of expressing algorithms as Boolean circuits and proving lower bounds on their complexity. But in 1993, it was proven that any proof along these lines must either rely on something very specialised about the algorithm in question that isn't broad enough to cover NP, or must involve defining some "non-constructive" property that is outside the realm of most of our mathematical experience. If any natural proof such as this could separate P and NP, then it would also violate a widely-believed but unproven conjecture about pseudo-random generators which would in turn allow us to find a fast way to do things like inverting one-way functions; this would be self-defeating, because it would mean that a natural proof showing that "hard" problems definitely involve slower algorithms than "easy" problems would also automatically produce a fast algorithm to solve a "hard" problem!
The next technique was arithmetisation, which effectively takes the Boolean field and embeds it into something larger so that it's possible to exploit more structure and correct some errors; this technique doesn't relativise, and there's another technique called diagonalisation (similar to that used by Georg Cantor to prove that the real numbers can't be put into a one-to-one correspondence with the natural numbers) which can be combined with it to evade both of the previous barriers. Unfortunately it turns out that even this isn't good enough: there's an additional barrier known as algebrisation, which is an extension of the previous notion of oracles to larger fields, and any proof relying on that is also unable to distinguish P from NP.
What now?
All it would take to demonstrate that P=NP would be just one polynomial-time algorithm for a problem known to be NP-complete, which includes problems that certainly have a great deal of practical applicability and so there's no shortage of incentive to find something. Lower bounds are harder to prove, and proving P≠NP would need to overcome the obstacles above and encode some very deep properties of computation. So it's not necessarily surprising that we don't have a proof yet, but also decent grounds for believing that P≠NP is the more likely answer.
P vs. NP is in fact a very deep question about the nature of mathematical thought. There's a beautiful version of the argument that runs something like this. Mathematical proofs are themselves computational objects if written with sufficient rigour; both theorem-proving software and proof checkers exist; and we know from general experience that it's easier to verify a proof than to create one, which is the essence of the distinction between P and NP. It may in fact be that the very reason it is hard to prove that P≠NP is because P≠NP.
This post is part of my December days series. Please prompt me!
no subject
no subject
Thank you!