homepage Welcome to WebmasterWorld Guest from 54.163.72.86
register, free tools, login, search, pro membership, help, library, announcements, recent posts, open posts,
Become a Pro Member
Home / Forums Index / Local / Foo
Forum Library, Charter, Moderators: incrediBILL & lawman

Foo Forum

    
P vs NP Solved?
Out of work bored, my attempt to solve p vs np
OnlineConnect




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

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.

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

 

lammert




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

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




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

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




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

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

Mack.

tedster




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

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




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

@jesec, @mack

The explanation in Wikpedia sucks. Try this from MIT:

[web.mit.edu ]

StoutFiles




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

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




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

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




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

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




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

@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




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

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




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

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




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

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.

Global Options:
 top home search open messages active posts  
 

Home / Forums Index / Local / Foo
rss feed

All trademarks and copyrights held by respective owners. Member comments are owned by the poster.
Home ¦ Free Tools ¦ Terms of Service ¦ Privacy Policy ¦ Report Problem ¦ About ¦ Library ¦ Newsletter
WebmasterWorld is a Developer Shed Community owned by Jim Boykin.
© Webmaster World 1996-2014 all rights reserved