The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Replies: 5   Last Post: Nov 2, 2009 4:29 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Keith Ramsay

Posts: 1,745
Registered: 12/6/04
Posted: Oct 29, 2009 2:19 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Oct 28, 7:01 pm, bill <> 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
|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 NP-problem, 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

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

|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.

The way that they define RP may sound like it's way
too stringent. But it's equivalent to much more lax

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
pseudo-random 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 re-run 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

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.