Welcome to WebmasterWorld Guest from **23.22.46.195**

Forum
Moderators: **incrediBILL & lawman **

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

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

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.

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.

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.

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

@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)

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.

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.

- Twitter Introduces The Best of Tweets With "Highlights"
- Google Inc. Q1, 2015 Results, Revenue was $17.3 billion
- Google Mobile Algo Roll-Out April 21, 2015
- Facebook tweaks News Feed to show more status updates from friends
- Yahoo and Microsoft Search Deal Now Includes Early Termination Clause
- Twitter Re-Enables Direct Messages Option From Non-Followers
- How Soon For a New Responsive Site to Appear in Google SERPs Showing "Mobile Friendly"
- Google Switches Mobile Search To Show Real-World Names
- Facebook: Mark Zuckerberg's Internet.org Project Under Fire
- comScore: Bing Breaks Through 20pct US Search Share, March 2015

- Google Mobile Algo Roll-Out April 21, 2015
- April 2015 AdSense Earnings and Observations
- Google Updates and SERP Changes - April 2015
- Influence of Brand and Usage on Google Serps
- Google announces 1st quarter AdSense numbers
- Google Switches Mobile Search To Show Real-World Names
- Google Mobile Algo to be Bigger Than Panda or Penguin as Deadline Looms
- Content Delivery Network and SEO Impact
- Matched content beta
- PR Update?

- Google Mobile Algo Roll-Out April 21, 2015
- April 2015 AdSense Earnings and Observations
- Google Updates and SERP Changes - April 2015
- Google Mobile Algo to be Bigger Than Panda or Penguin as Deadline Looms
- Influence of Brand and Usage on Google Serps
- Google Switches Mobile Search To Show Real-World Names
- Google announces 1st quarter AdSense numbers
- Content Delivery Network and SEO Impact
- Matched content beta
- PR Update?