Welcome to WebmasterWorld Guest from 54.224.184.33

Forum Moderators: incrediBILL & lawman

Message Too Old, No Replies

# P vs NP Solved?

## Out of work bored, my attempt to solve p vs np

#### OnlineConnect

12:32 am on Apr 29, 2010 (gmt 0)

#### Junior Member

joined:Feb 21, 2010
posts:47

So here I was no job no company and I was browsing on the internet and came across the P vs NP problem. Now maybe I didn't fully appreciate the complexity of p vs np but when I read the example question I thought "I'll have a bash at that, 1 million squid lovely, will keep me off the streets."

So I loaded MAMP up on my Apple as had no server at the time and wrote a program that solved the P vs NP example problem. Excitedly I emailed it the Clay Institute for my reward. Feeling pretty confident I would receive world acclaim and then drop a bombshell on where I got the list of names from....hehee. But it appears solving the example question doesn't mean you have solved P vs NP...... Ah sa la vie.... :( Anyway here is my effort for the world to see and the question posed by the Clay Institute. You can try it on any server with php and mysql and it does solve the example question posed.

Example Question:
Suppose that you are organizing housing accommodations for a group of 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 impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.

OK webmasterworld server just had overload when I tried to paste it all at once so I will paste it in parts......

#### lammert

12:55 pm on Apr 29, 2010 (gmt 0)

#### Senior Member from KZ

joined:Jan 10, 2005
posts: 2935

Waiting for the next post. Giving a mathematical watertight solution for the N vs. NP problem would bring you to the status of Einstein. :) Unfortunately there is no Nobel price yet for strict mathematical achievements.

You just need to know that many NP problems have easy solutions for most of their input sets. But your proof has to be that there is a solution method which takes a maximum polynomial time to solve for all possible input sets. A Monte Carlo simulation where you use a number of random examples as a test doesn't therefore count as proof. There may be one single situation where your algorithm doesn't execute in polynomial time.

A well known situation (not an NP problem by the way) where average solution speed and worst-case solution speed are not the same is the quick sort algorithm. The average solution takes O(N*logN) time, but worst case it takes O(N*N) time.

#### jecasc

8:57 pm on Apr 29, 2010 (gmt 0)

#### Senior Member

joined:May 8, 2003
posts:1141

Actually this is the first time I hear of P vs. NP. I looked it up in wikipedia and noticed this is so complex that I was not even able to understand the problem.

#### mack

9:10 pm on Apr 29, 2010 (gmt 0)

#### Moderator from GB

joined:June 15, 2001
posts:7684

jecasc, I'm glad you said that. I don't feel quite as bad now.

Mack.

#### tedster

4:31 am on Apr 30, 2010 (gmt 0)

#### Senior Member

joined:May 26, 2000
posts:37301

You're as much of a geek as I am! I've been working on the Riemann Conjecture for decades... as a hobby.

That's another famous unsolved problem with a million dollar prize from the Clay Institute. But I don't work on it for any money. I work on it because it's just one of the wonders of existence like a black hole or a pulsar.

#### graeme_p

5:26 am on May 1, 2010 (gmt 0)

#### Senior Member from GB

joined:Nov 16, 2005
posts:2680

@jesec, @mack

The explanation in Wikpedia sucks. Try this from MIT:

[web.mit.edu ]

#### StoutFiles

2:08 pm on May 1, 2010 (gmt 0)

#### Senior Member

joined:May 6, 2008
posts:2011

xample Question:
Suppose that you are organizing housing accommodations for a group of 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 impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.

Tackled this problem 3 years ago and solved it in C++. Brought it to to the CS chair at my college and, while convinced I had solved this particular problem, he was not convinced I had solved P vs NP with my approach. Turns out he was right as harder problems couldn't be solved with it.

You really want to solve P vs NP? There are "traveling salesman" problems out there with enormous amounts of points and answers that have taken an extraordinary amount of time to generate with multiple powerful computers. If you think you've solved it, then test your approach on one of those problems.

#### ofnimira

4:24 pm on May 1, 2010 (gmt 0)

#### New User

joined:Nov 27, 2004
posts:9

There's something odd going on here. There's a large class of problems known as NP-complete problems, and if you can solve any NP complete problem in polynomial time then P=NP. If the example problem is not NP-complete then why didn't they choose a problem which was?

#### lammert

10:25 pm on May 1, 2010 (gmt 0)

#### Senior Member from KZ

joined:Jan 10, 2005
posts: 2935

I think some of the confusion here is that a solution in a software algorithm is not the same as a mathematical proof. You can write a program which solves many, or maybe even most of the input sets within a polynomial time for an NP complete problem, but that is not the same as what mathematicians need. They want the proof that there exists no input set that can not be solved in polynomial time for that problem. Even if there is only one such input set, the mathematical proof fails, but the algorithm may virtually always give an answer in polynomial time.

#### graeme_p

9:00 am on May 2, 2010 (gmt 0)

#### Senior Member from GB

joined:Nov 16, 2005
posts:2680

@lammert, I thought the same as ofnimra: if you can solve one NP complete problem in polynomial time, then you can solve any NP complete problem in polynomial time. The problem is that this particular example is not NP complete. It is not NP hard (because StoutFiles says his solution could not solve harder problems)

#### StoutFiles

1:12 pm on May 2, 2010 (gmt 0)

#### Senior Member

joined:May 6, 2008
posts:2011

The problem is that this particular example is not NP complete. It is not NP hard (because StoutFiles says his solution could not solve harder problems)

The problem with it is the freedom to set your own list of incompatible students...you can make the problem as easy as you want to solve it quickly. It is a horrible example problem; it should come with a very complicated incompatible list and an answer key to check your work.

Anyone wishing to solve P vs NP and become a computer legend should go here.
[tsp.gatech.edu...]
They have plenty of test data with their current "optimal solutions"...if you can get their solution (or better) in polynomial time with multiple data sets THEN you should come back and claim victory on the hardest puzzle programming has to offer.

#### graeme_p

4:08 pm on May 2, 2010 (gmt 0)

#### Senior Member from GB

joined:Nov 16, 2005
posts:2680

That sounds like it means a satisfactory solution have to solve it with a any list incompatible students, that was actually solvable, and also identify unsolvable ones in P?

I will bookmark that link in case I have a few years to spare some time!

#### lammert

9:38 pm on May 2, 2010 (gmt 0)

#### Senior Member from KZ

joined:Jan 10, 2005
posts: 2935

Yes, and in practice this means that every solution in the form of an algorithm with test data is unable to proof the P vs. NP problem. With an algorithmical solution for this problem you have to test all possible lists of incompatible students and that is impossible in the short life time we have.

The only real proof can be given with a mathematical analysis.