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.

]]>http://arxiv.org/pdf/0905.2213

Thanx.

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

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

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

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

Does it stand up OK?

I suggest replacing logarithmically with **exponentially**.

Does it stand up OK?

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

]]>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?

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

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

]]>