You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**mikau****Member**- Registered: 2005-08-22
- Posts: 1,504

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.

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

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

Offline

**TheDude****Member**- Registered: 2007-10-23
- Posts: 361

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

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

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.

Offline

**MathsIsFun****Administrator**- Registered: 2005-01-21
- Posts: 7,619

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

Does it stand up OK?

Offline

**JaneFairfax****Member**- Registered: 2007-02-23
- Posts: 6,868

MathsIsFun wrote:

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

Does it stand up OK?

I suggest replacing logarithmically with **exponentially**.

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

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.

Offline

**MathsIsFun****Administrator**- Registered: 2005-01-21
- Posts: 7,619

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 (n-1)! since it matter not where you start. But perhaps this fact should be excluded.

Thanks

Offline

**mathsyperson****Moderator**- Registered: 2005-06-22
- Posts: 4,900

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.

Offline

**MathsIsFun****Administrator**- Registered: 2005-01-21
- Posts: 7,619

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

Offline

**JaneFairfax****Member**- Registered: 2007-02-23
- Posts: 6,868

JaneFairfax wrote:

MathsIsFun wrote: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)*

Offline

**MathsIsFun****Administrator**- Registered: 2005-01-21
- Posts: 7,619

Sorry, Jane. Yes I did, and have corrected it, but not uploaded it yet. Thanks.

Offline

**Eduardo H****Member**- Registered: 2009-05-14
- Posts: 1

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.

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

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.

Offline

Pages: **1**