Welcome to WebmasterWorld Guest from **50.17.5.36**

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.

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

Mack.

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.

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?

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.

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!

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.

- Register For Free! -
**Become a Pro Member!** - See forum categories - Enter the Forum

- Moderator List | Top Contributors:This Week, This Month, Jan, Dec, Archive, Top 100 All Time, Top Voted Members

- February 2016 AdSense Earnings and Observations
- Google Updates and SERP Changes - Feb 2016
- What to do When a Site Drops in Google's SERPs
- My site's being de-indexed and replaced by others
- Opera In $1.2 Billion Buyout Offer
- Report: LinkedIn Stock Dropped $10-billion
- France Tells Facebook To Stop Tracking Non-Users Without Consent
- Google Targeting Bad Ads With New Deceptive Site Label
- The Head Of Google Search, Amit Singhal Is Leaving The Company
- Booting the Botnets

- Twitter's New Timeline Option Inserts "Best Tweets First"
- Bing Working to Fix Bing Ads Data Reporting Problem
- Opera In $1.2 Billion Buyout Offer
- Twitter Announces Trust and Safety Council To Tackle Trolls
- France Tells Facebook To Stop Tracking Non-Users Without Consent
- What to do When a Site Drops in Google's SERPs
- Report: LinkedIn Stock Dropped $10-billion
- Google Targeting Bad Ads With New Deceptive Site Label
- Facebook Says Its Version of Six Degrees of Separation is Three Point Five
- The Head Of Google Search, Amit Singhal Is Leaving The Company