Math Is Fun Forum

mikau

Member

Registered: 2005-08-22

Posts: 1,504

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 (2008-04-29 01:06:15)

---

A logarithm is just a misspelled algorithm.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

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 NP-complete, what you must do is take a known NP-complete 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 NP-complete 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 NP-complete problem is a problem for which every other problem in NP (not just NP-complete) can be reduced to in polynomial time.  That means if you can solve one NP-complete 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..."

TheDude

Member

Registered: 2007-10-23

Posts: 361

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 NP-complete.  Question for Ricky: what's the difference between NP and NP-complete?  Is it that every problem in NP can be reduced in polynomial time to a problem in NP-complete, but not every problem in NP can be reduced to another problem in NP?

---

Wrap it in bacon

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: P vs NP?

Is it that every problem in NP can be reduced in polynomial time to a problem in NP-complete, 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 3-sat, the first NP-complete 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

Registered: 2005-01-21

Posts: 7,713

Re: P vs NP?

I did a "quick and dirty" intro here: NP-Complete - 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

Member

Registered: 2007-02-23

Posts: 6,868

Re: P vs NP?

I did a "quick and dirty" intro here: NP-Complete - A Rough Guide

Does it stand up OK?

I suggest replacing “logarithmically” with exponentially.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

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 (n-1)! 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

Registered: 2005-01-21

Posts: 7,713

Re: P vs NP?

I don't like the wording.  You make P and NP sound mutually exclusive.

Really? Do you have a suggested rewording?

The graph in the traveling sales man problem is not complete.  And the execution time is technically (n-1)! 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

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

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

Registered: 2005-01-21

Posts: 7,713

Re: P vs NP?

Clear pipes, and drip-activated photo. But would the photo be enough?

---

"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: P vs NP?

I did a "quick and dirty" intro here: NP-Complete - A Rough Guide

Does it stand up OK?

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 (2008-04-30 21:59:43)

MathsIsFun

Administrator

Registered: 2005-01-21

Posts: 7,713

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

Eduardo H

Member

Registered: 2009-05-14

Posts: 1

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

Registered: 2005-12-04

Posts: 3,791

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