| Line 1: | Line 1: | ||
| − | '''<big>Group I | + | '''<big>Group I''' |
| − | P vs NP: a Clay Millennium Problem with Economic Flavor</big>''' | + | '''P vs NP: a Clay Millennium Problem with Economic Flavor</big>''' |
'''The Problem Statement''' | '''The Problem Statement''' | ||
| + | |||
P = NP? | P = NP? | ||
| + | |||
P vs. NP is perhaps one of the biggest open problems in computer science and mathematics but what is P vs NP?. The following question of interest to people working with computer science and mathematics in: Can every solved problem whose answer can be checked quickly by a computer also be quickly solved by a computer? P and NP could be defined as the two types of maths problems referred to: P problems are fast for computers to solve, and so are considered "easy". NP problems are fast (and so "easy") for a computer to check, but are not necessarily easy to solve. But so far, no one’s been able to decisively answer the question one way or the other. Frequently called the most important outstanding question in theoretical computer science, the equivalency of P and NP is one of the seven problems that the Clay Mathematics Institute will give you a million dollars for proving — or disproving. | P vs. NP is perhaps one of the biggest open problems in computer science and mathematics but what is P vs NP?. The following question of interest to people working with computer science and mathematics in: Can every solved problem whose answer can be checked quickly by a computer also be quickly solved by a computer? P and NP could be defined as the two types of maths problems referred to: P problems are fast for computers to solve, and so are considered "easy". NP problems are fast (and so "easy") for a computer to check, but are not necessarily easy to solve. But so far, no one’s been able to decisively answer the question one way or the other. Frequently called the most important outstanding question in theoretical computer science, the equivalency of P and NP is one of the seven problems that the Clay Mathematics Institute will give you a million dollars for proving — or disproving. | ||
| Line 26: | Line 28: | ||
| − | '''Examples''' | + | '''Examples in P vs. NP Problem''' |
| + | |||
The following examples describe problems that currently involve taking exponential time to find a solution exactly or using an approximation of the solution to solve quickly. If P=NP, these problems could then be solved both quickly and exactly. | The following examples describe problems that currently involve taking exponential time to find a solution exactly or using an approximation of the solution to solve quickly. If P=NP, these problems could then be solved both quickly and exactly. | ||
* Long simple paths | * Long simple paths | ||
| + | |||
A simple path in a graph is just one without any repeated edges or vertices and to define the problem of finding the longest path in terms of complexity theory, we need to formalize it as yes or no question: given a graph G, vertices s and t and number k , does there exist a simple path from s to t with at least k edges? A solution to this problem would then consist of such a path . | A simple path in a graph is just one without any repeated edges or vertices and to define the problem of finding the longest path in terms of complexity theory, we need to formalize it as yes or no question: given a graph G, vertices s and t and number k , does there exist a simple path from s to t with at least k edges? A solution to this problem would then consist of such a path . | ||
If you are given a path, you can quickly look at it and add up the length, double checking that it really is a path with length at least k. This can all be done in linear time, so certainly it can be done in polynomial time. However we don't know whether this problem is in P. In fact this problem is NP-complete, so we believe that no such algorithm exists other than using brute force. | If you are given a path, you can quickly look at it and add up the length, double checking that it really is a path with length at least k. This can all be done in linear time, so certainly it can be done in polynomial time. However we don't know whether this problem is in P. In fact this problem is NP-complete, so we believe that no such algorithm exists other than using brute force. | ||
* Chess | * Chess | ||
| + | |||
What is involved in chess programming? Essentially the sequences of moves possible form a tree: the first player has a choice of 20 different moves( most of which are not very good), after each of which the second player has a choice of many responses, and so on. Chess playing programs work by traversing this tree, and finding what the possible consequences would be of each different move. | What is involved in chess programming? Essentially the sequences of moves possible form a tree: the first player has a choice of 20 different moves( most of which are not very good), after each of which the second player has a choice of many responses, and so on. Chess playing programs work by traversing this tree, and finding what the possible consequences would be of each different move. | ||
The tree of moves is not very deep, as a typical chess game might last 40 moves, and it is rare for one to reach 200 moves. Since each move involves a step by each player, there are at most 400 positions involved in most games. If we traversed the tree of chess positions only to that depth, we would only need enough memory to store the 400 positions on a single path at a time. This much memory is available even on the smallest computers you are likely to use. So perfect chess playing is a problem in PSPACE. (Actually one must be more careful in definitions. There is only a finite number of positions in chess, so in principle you could write down the solution in constant time. But that constant would be very large. Generalized versions of chess on larger boards are in PSPACE.) | The tree of moves is not very deep, as a typical chess game might last 40 moves, and it is rare for one to reach 200 moves. Since each move involves a step by each player, there are at most 400 positions involved in most games. If we traversed the tree of chess positions only to that depth, we would only need enough memory to store the 400 positions on a single path at a time. This much memory is available even on the smallest computers you are likely to use. So perfect chess playing is a problem in PSPACE. (Actually one must be more careful in definitions. There is only a finite number of positions in chess, so in principle you could write down the solution in constant time. But that constant would be very large. Generalized versions of chess on larger boards are in PSPACE.) | ||
| Line 39: | Line 44: | ||
* Knapsack Problem | * Knapsack Problem | ||
| + | |||
One of the easier NP-Complete problems to describe is the knapsack problem. You are given n objects each with different weights and values and you have a knapsack that can only hold so much weight. You want to put objects into the knapsack such that you maximize the value of the knapsack. The only way we currently know how to solve this is try nearly every combination of the items in order to see which set has the most value. In other words, we need to make nearly every calculation possible in order to find the answer. This solution takes time exponential to the number of items to solve. Meanwhile if given the items that would add up to the most value while still fitting in the knapsack, one could quickly see that replacing any item would either add more weight than the knapsack could handle or reduce the value of the knapsack. This can be done just by looking at each item once, making the solution rather quick to find. If P=NP is true however, this would indicate that there is some solution such that the knapsack problem could be created in less than exponential time. | One of the easier NP-Complete problems to describe is the knapsack problem. You are given n objects each with different weights and values and you have a knapsack that can only hold so much weight. You want to put objects into the knapsack such that you maximize the value of the knapsack. The only way we currently know how to solve this is try nearly every combination of the items in order to see which set has the most value. In other words, we need to make nearly every calculation possible in order to find the answer. This solution takes time exponential to the number of items to solve. Meanwhile if given the items that would add up to the most value while still fitting in the knapsack, one could quickly see that replacing any item would either add more weight than the knapsack could handle or reduce the value of the knapsack. This can be done just by looking at each item once, making the solution rather quick to find. If P=NP is true however, this would indicate that there is some solution such that the knapsack problem could be created in less than exponential time. | ||
| Line 45: | Line 51: | ||
'''Reference''' | '''Reference''' | ||
| + | |||
* Cook, Stephen (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158. | * Cook, Stephen (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158. | ||
* Hambrusch, Susanne (2015). CS 381 Lecture - NP and P. Retrieved from notes taken in lecture. | * Hambrusch, Susanne (2015). CS 381 Lecture - NP and P. Retrieved from notes taken in lecture. | ||
Revision as of 13:46, 22 April 2016
Group I P vs NP: a Clay Millennium Problem with Economic Flavor
The Problem Statement
P = NP?
P vs. NP is perhaps one of the biggest open problems in computer science and mathematics but what is P vs NP?. The following question of interest to people working with computer science and mathematics in: Can every solved problem whose answer can be checked quickly by a computer also be quickly solved by a computer? P and NP could be defined as the two types of maths problems referred to: P problems are fast for computers to solve, and so are considered "easy". NP problems are fast (and so "easy") for a computer to check, but are not necessarily easy to solve. But so far, no one’s been able to decisively answer the question one way or the other. Frequently called the most important outstanding question in theoretical computer science, the equivalency of P and NP is one of the seven problems that the Clay Mathematics Institute will give you a million dollars for proving — or disproving.
Background
In 1956, Kurt Gödel wrote a letter to John von Neumann. In this letter, Gödel asked whether a certain NP complete problem could be solved in quadratic or linear time. And in 1971, Stephen Cook introduced the precise statement of the P vs. NP problem in the article called “The complexity of theorem proving procedures”.
Importance
There are lots of P and NP problems in our daily applications, especially the NP problems, which means that people don’t obtain a idea for how to solve in a method that is faster than testing every possible answer. Most people instead of waiting for this solution choose to approximate the solution instead. They get the solution quickly but with some error involved. Most problems relating to the maximum value possible lie in NP and thus are not always worth the time to compute. This means that people are generally not using their resources to receive the largest possible value.
Existing Theories
As said earlier, P problems are ones that can be solved quickly or in polynomial time. This means that there are generally better methods than brute force to solve this problem or that the brute force method does not take exponential time. NP problems are all problems whose solution can be checked in polynomial time. The classification of NP does entail all P problems. However, NP problems are not necessarily solved quickly. There is a subset of problems in NP called NP-Complete. These are the hardest problems that still lie in NP. They require at least exponential time to solve. By virtue of being the hardest, if these were shown to have quick solutions, it would imply that all problems in NP have a quick solution. So NP-completeness can be thought of as a way of making the big P=NP question equivalent to smaller questions about the hardness of individual problems. NP-Complete problems are all related as well; by manipulating the input structures, every problem in NP-Complete can be solved using any other NP-Complete solution method.
So if we believe that P and NP are unequal, and we prove that some problem is NP-complete, we should believe that it doesn't have a fast algorithm. For unknown reasons, most problems we've looked at in NP turn out either to be in P or NP-complete. So the theory of NP-completeness turns out to be a good way of showing that a problem is likely to be hard, because it applies to a lot of problems. But there are problems that are in NP, not known to be in P, and not likely to be NP-complete. We should ask ourselves, why should we care ? These NP-complete problems really come up all the time. Knowing they are hard, allows you to make the choice of whether it is worth the time to solve exactly or would it be better to solve the problem approximately and quickly. It is possible to come up with a provably fast algorithm , that does not solve the problem correctly but comes up with a solution that you can prove is close to right.
Examples in P vs. NP Problem
The following examples describe problems that currently involve taking exponential time to find a solution exactly or using an approximation of the solution to solve quickly. If P=NP, these problems could then be solved both quickly and exactly.
- Long simple paths
A simple path in a graph is just one without any repeated edges or vertices and to define the problem of finding the longest path in terms of complexity theory, we need to formalize it as yes or no question: given a graph G, vertices s and t and number k , does there exist a simple path from s to t with at least k edges? A solution to this problem would then consist of such a path . If you are given a path, you can quickly look at it and add up the length, double checking that it really is a path with length at least k. This can all be done in linear time, so certainly it can be done in polynomial time. However we don't know whether this problem is in P. In fact this problem is NP-complete, so we believe that no such algorithm exists other than using brute force.
- Chess
What is involved in chess programming? Essentially the sequences of moves possible form a tree: the first player has a choice of 20 different moves( most of which are not very good), after each of which the second player has a choice of many responses, and so on. Chess playing programs work by traversing this tree, and finding what the possible consequences would be of each different move. The tree of moves is not very deep, as a typical chess game might last 40 moves, and it is rare for one to reach 200 moves. Since each move involves a step by each player, there are at most 400 positions involved in most games. If we traversed the tree of chess positions only to that depth, we would only need enough memory to store the 400 positions on a single path at a time. This much memory is available even on the smallest computers you are likely to use. So perfect chess playing is a problem in PSPACE. (Actually one must be more careful in definitions. There is only a finite number of positions in chess, so in principle you could write down the solution in constant time. But that constant would be very large. Generalized versions of chess on larger boards are in PSPACE.) The reason this deep game-tree search method can't be used in practice is that the tree of moves branches a lot, so that even though it is not deep it has an enormous number of vertices. We won't run out of space if we try to traverse it, but we will run out of time before we get even a small fraction of the way through. Some pruning methods, notably "alpha-beta search" can help reduce the portion of the tree that needs to be examined, but not enough to solve this difficulty. For this reason, actual chess programs instead only search a much smaller depth (such as up to 7 moves), at which point they don't have enough information to evaluate the true consequences of the moves and are forced to guess by using heuristic "evaluation functions" that measure simple quantities such as the total number of pieces left.
- Knapsack Problem
One of the easier NP-Complete problems to describe is the knapsack problem. You are given n objects each with different weights and values and you have a knapsack that can only hold so much weight. You want to put objects into the knapsack such that you maximize the value of the knapsack. The only way we currently know how to solve this is try nearly every combination of the items in order to see which set has the most value. In other words, we need to make nearly every calculation possible in order to find the answer. This solution takes time exponential to the number of items to solve. Meanwhile if given the items that would add up to the most value while still fitting in the knapsack, one could quickly see that replacing any item would either add more weight than the knapsack could handle or reduce the value of the knapsack. This can be done just by looking at each item once, making the solution rather quick to find. If P=NP is true however, this would indicate that there is some solution such that the knapsack problem could be created in less than exponential time.
The Future of N vs. NP Problem
Reference
- Cook, Stephen (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158.
- Hambrusch, Susanne (2015). CS 381 Lecture - NP and P. Retrieved from notes taken in lecture.
