
 mikau
 Super Member
P vs NP?
In my data structures course last semester, my teacher gave a handout (which by now is who knows where) explaining the P vs Np....Np complete or whatever it is, problem.
I kinda sorta get it. Essentially they're a special class of problems that no one's able to solve in polynomial time, but no one's been able to prove they are not polynomial time.
The article gave an example of the task of placing a collection of students in row of contiguous dorm rooms, and you are given a list of people that cannot be next to eachother. The task is to determine if any arrangment exists, and if so, what the arrangement is in polynomial time.
Is this really an NP complete problem? I'm sure whatever was on that paper was corrrect, i just don't remember the exact details. One thing i'm really uncertain about here is the maxium size of the list. For n students, you can have..what, n choose 2 possible imcompatible pairs? Or does the list contain no more than n incompatible pairs..
has anyone heard of this problem?
My other question is, would solving any single np complete problem consitute a universal solution? Or does it require a more general proof? It seems like that student sorting assignment could be solved in polynomial time with some though, unless perhaps the list size can be n choose 2.
Last edited by mikau (20080429 23:06:15)
A logarithm is just a misspelled algorithm.
 Ricky
 Moderator
Re: P vs NP?
The easiest way to see NP is with an alternate definition (not sure if you were given this one):
P: Solution can be found in polynomial time. NP: Solution can be verified in polynomial time.
In your problem, if someone walked up to you can told you "here is my solution", can you check to see if it works in polynomial time? If the answer is yes, then you are in NP.
It should be quite clear that any problem in P is also in NP. If you can find a solution in polynomial time, you can certainly verify it in polynomial time.
Now to prove that your problem is in NPcomplete, what you must do is take a known NPcomplete problem, and transform a general instance of it in polynomial time to a single instance of your problem, then show that a solution exists in this instance if and only if it there is a solution in the NPcomplete problem.
Your problem sounds like graph coloring, though there is one unclear detail. Is this list of people like:
Bob Judy Bill Jane Bozo Julie
And none of them can be next to each other? Or is it:
Bob Judy Bill Jane Bozo Julie
And only pairs can't be next to each other?
My other question is, would solving any single np complete problem consitute a universal solution? Or does it require a more general proof?
An NPcomplete problem is a problem for which every other problem in NP (not just NPcomplete) can be reduced to in polynomial time. That means if you can solve one NPcomplete problem in polynomial time, you can reduce any other problem to it in polynomial time, hence solving that problem in polynomial time as well.
So in short, yes.
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
Re: P vs NP?
It sounds like he's given a list of names of students, each of whom has a list of other students that they cannot live next to. The example would then be:
Bob Judy Bill Jane Bozo Julie
Bob cannot live next to: Judy Bozo
Judy cannot live next to: Bob
Bill cannot live next to: Jane Bozo Julie
Jane cannot live next to: Bill Julie
Bozo cannot live next to: Bob Bill
Julie cannot live next to: Bill Jane
I've never heard of this particular problem, but at first glance it appears to be at least NP, if not NPcomplete. Question for Ricky: what's the difference between NP and NPcomplete? Is it that every problem in NP can be reduced in polynomial time to a problem in NPcomplete, but not every problem in NP can be reduced to another problem in NP?
Wrap it in bacon
 Ricky
 Moderator
Re: P vs NP?
Is it that every problem in NP can be reduced in polynomial time to a problem in NPcomplete, but not every problem in NP can be reduced to another problem in NP?
That is correct. For example, we know of no way to reduce the graph coloring problem to sorting a list. On the other hand, every problem in NP can be reduced to 3sat, the first NPcomplete problem.
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
 MathsIsFun
 Administrator
Re: P vs NP?
I did a "quick and dirty" intro here: NPComplete  A Rough Guide
Does it stand up OK?
"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  Leon M. Lederman
 JaneFairfax
 Legendary Member
Re: P vs NP?
I suggest replacing “logarithmically” with exponentially.
Q: Who wrote the novels Mrs Dalloway and To the Lighthouse? A: Click here for answer.
 Ricky
 Moderator
Re: P vs NP?
So, programs that take dramatically longer as the problem gets harder (ie not in "P") could be solved quickly on this amazing "N" computer and so are in "NP".
I don't like the wording. You make P and NP sound mutually exclusive.
The graph in the traveling sales man problem is not complete. And the execution time is technically (n1)! since it matter not where you start. But perhaps this fact should be excluded.
I wonder if a network of pipes might help? Just pour the water into the top and see which path provides the first drip of water out the bottom?
Pipes can't be constructed in "P" time.
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
 MathsIsFun
 Administrator
Re: P vs NP?
Ricky wrote:I don't like the wording. You make P and NP sound mutually exclusive.
Really? Do you have a suggested rewording?
Ricky wrote:The graph in the traveling sales man problem is not complete. And the execution time is technically (n1)! since it matter not where you start. But perhaps this fact should be excluded.
Thanks
"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  Leon M. Lederman
Re: P vs NP?
Would the pipe system work? I'd imagine you'd be able to time how long the water took to reach the end, and so know how long the shortest path was, but you'd still have no idea which path the water took.
Why did the vector cross the road? It wanted to be normal.
 MathsIsFun
 Administrator
Re: P vs NP?
Clear pipes, and dripactivated photo. But would the photo be enough?
"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  Leon M. Lederman
 JaneFairfax
 Legendary Member
Re: P vs NP?
JaneFairfax wrote:I suggest replacing “logarithmically” with exponentially.
MathsIsFun, did you see my post? If time increases logarithmically, it would actually be faster than polynomial time. (The graph of y = ln(x) lies below that of y = x.) However, if you are talking about processes that take longer than polynomial time, you mean they are increasing exponentially.
Last edited by JaneFairfax (20080501 19:59:43)
Q: Who wrote the novels Mrs Dalloway and To the Lighthouse? A: Click here for answer.
 MathsIsFun
 Administrator
Re: P vs NP?
Sorry, Jane. Yes I did, and have corrected it, but not uploaded it yet. Thanks.
"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  Leon M. Lederman
Re: P vs NP?
I am really an outsider of this realm. Yet, I do find interesting the P vs NP question. I have written something on the difficulty of solving SAT, can somebody give an opinion ?
http://arxiv.org/pdf/0905.2213
Thanx.
 Ricky
 Moderator
Re: P vs NP?
I do not believe you explain your sorting technique thoroughly enough. You assign numbers A=1, !A = 2, B = 3, !B = 4, and so on, but how does this assign a number to a triple such as:
A + B + !C
Intuition suggests what you're going for is 1 + 3 + 6 = 10, but then I don't see how sorting this makes reducible triples adjacent to one another.
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
