Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: NP PROBLEMS
Posted:
Oct 29, 2009 2:19 AM


On Oct 28, 7:01 pm, bill <b92...@yahoo.com> wrote: The following problem is cited as a typical P vs NP problem.
These are just called NP problems.
"Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NPproblem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical.
I would put a period after the parenthetical remark there. The ease of checking a possible solution is part of the explanation of what "NP" means here. The fact that it seems hard to find an actual solution is not. Easy problems are in NP as well.
Technically also, the problem that is in NP here is not that of finding a solution, but simply, given the list of incompatible pairs of students, determine whether it is possible to make an assignment (yes or no). Of course it's very closely related to the problem of finding a solution.
[...] This problem has many solutions; of which only one is required. It seems to me that the length of the problem should be mitigated by the number of possible solutions.
"Length"? Perhaps you mean the difficulty or the time required to solve it?
You might be interested in a problem class known as RP, for "random polynomial". If whenever there exists a solution, there are enough solutions to ensure that picking possible solutions at random is likely to find a valid solution quickly, then the problem lies in RP.
http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#rp
The way that they define RP may sound like it's way too stringent. But it's equivalent to much more lax requirements.
Suppose that you have a problem where you know that either there isn't a solution, or you know that 1/n^2 of the possible solutions work (where n is the number of bits required to represent the problem). This algorithm for checking solutions doesn't satisfy their definition because 1/n^2 is generally far less than 1/2. But there's another algorithm we could use. Make a second algorithm that is like the first, but checks a batch of 2*n^2 possible solutions and counts it as a success if any of them work. Now we have an algorithm where over 1/2 of the possible inputs to the algorithm work if any of them do. The problem (does a solution exist) is the same in either case. So we still consider the original problem to lie in RP. The same argument would work just as well if I had 1/n^3, 1/n^4, etc.
By searching for a longer period of time on randomly selected potential solutions, one could then guarantee that the probability of not finding a solution when one exists is extremely small.
[...] IMMHO, a problem should be considered NP if and only if the probability of loss equals or exceeds a specified value. This could be a sliding scale based upon the total number of possible outcomes.
Well, since NP includes all the easy problems too, this probably isn't quite what you mean to say.
I think it's generally believed that P=RP, hence roughly that if a problem is guaranteed to have enough solutions whenever it has any, then it's not too hard. One reason to believe this is that it's thought you can produce pseudorandom number generators that are good enough to make the above search consistently work in polynomial time. (If I have a real random number generator, I can search with it long enough that my probability of ever failing to find a solution when one exists is small, even if you give me each possible problem in order, just as long as you don't make me rerun the same problem more than once. Even if there are finitely many cases where the algorithm fails, we can patch over them.)
So for a problem in NP not to fall into P, probably it can't be in RP. To avoid being in RP, when a solution exists, the fraction of potential solutions that work has to fall below 1/n^2 sometimes (and also 1/n^3, 1/n^4, etc.)
Usually people are talking about problems where the number of possible solutions could be just 1, and where the number is typically "exponentially small", 1/2^{cn} for some positive constant c.
Keith Ramsay



