| Author |
Message
|
| DivideByZero |
 Posted: Tue Mar 25, 2008 1:02 pm Post subject: explanation of the n=np problem please |
 |
|
Forum Sophomore
Joined: 02 Dec 2007
Posts: 171
|
Hi, I read a thread in this forum (in the pseudoscience section) talking about the famous N=?NP problem. I have seen this and tried to understand this but it doesn't make sense yet.
Can someone please explain this famous problem in simpler terms (like very simple terms)?
I know it has something to do with what is faster: finding the formula or checking if its right? |
|
| Back to top |
|
 |
| serpicojr |
| Posted: Wed Mar 26, 2008 12:06 pm Post subject: |
|
|
Forum Ph.D.
Joined: 17 Jul 2007
Posts: 871
Location: JRZ
|
I don't know a lot about it myself, but let me take a stab. Consider a yes-or-no problem which takes n inputs. For example, given a set S of n distinct, positive integers and another integer k, can you write k as the sum of distinct elements of S? Suppose that the answer to our problem is yes. There are two main things we'd like to do in the context of this problem:
1. decide whether potential solutions are correct;
2. produce solutions
The former is an easier thing than the latter: when you produce a potential solution, you have to be able to decide whether it's true!
Suppose we have some algorithms to do 1. and 2. Oftentimes you can describe the time it takes to perform these algorithms as a function of the number of inputs n. (By "time" I really mean "how many calculations you have to perform".) For each problem, there are good algorithms (fast ones) and bad algorithms (slow ones). We can speak of the minimal amount of time it takes to complete 1. or 2. as being the running times of the best algorithms that exist, and we consider this minimal time to be the complexity of the problem. We can then break problems into "classes" based upon the complexity of 1. and 2.
Two important notions of speed of algorithms we're interested in are polynomial and non-polynomial time. An algorithm is polynomial time if the number of steps it takes is (less than or equal to) a polynomial in the number of inputs n, e.g. n, n2, n20+3n7, etc. An algorithm is polynomial time if it runs much faster, too--for example, log(n) is much faster, so this is polynomial time. An algorithm which is not polynomial time is... non-polynomial time. In other words, the number of steps grows faster than any polynomial as the number of inputs increases.
Now we define P and NP. NP is the set of problems where 1. has polynomial time complexity. P is the subset of NP where 2. also has polynomial time complexity. The question, then, is whether P is all of NP or whether there exist "hard" problems for which 2. is non-polynomial time. The traveling salesman problem (TSP) is an example of such.
So our poster was claiming that he had shown P = NP by finding solutions to TSP in polynomial time. I believe I debunked him. |
|
| Back to top |
|
|
| DivideByZero |
| Posted: Wed Mar 26, 2008 3:15 pm Post subject: |
|
|
Forum Sophomore
Joined: 02 Dec 2007
Posts: 171
|
interesting, thanks!
and good job on your debunk, lol. |
|
| Back to top |
|
|
| sunshinewarrior |
| Posted: Thu Mar 27, 2008 3:46 am Post subject: |
|
|
Forum Ph.D.
Joined: 26 Sep 2007
Posts: 837
Location: London
|
| serpicojr wrote: |
So our poster was claiming that he had shown P = NP by finding solutions to TSP in polynomial time. I believe I debunked him. |
Yup. Thanks for the debunk. I believed it sounded to good to be true but didn't have the maths enough to challenge the way you did. |
|
| Back to top |
|
|
| Mathew Cherian |
| Posted: Thu Apr 03, 2008 11:00 am Post subject: |
|
|
Forum Freshman
Joined: 18 Mar 2008
Posts: 41
Location: India
|
Dear Serpicojr,
I don't think you debunked me. I got all the more sure that my solution is ok. We had a few conversations and I believe in one you said if you do all the routes then it is ok. Then I don't know why you feel you debunked me when my answer was yes.
Also it seems you cannot use the word non polynomial time it should be non deterministic polynomial time otherwise you will be considered as not aware of the whole subject properly let alone debunk a solution ot this kind of a problem.
Mathew Cherian |
|
| Back to top |
|
|
| Mathew Cherian |
| Posted: Thu Apr 03, 2008 11:08 am Post subject: |
|
|
Forum Freshman
Joined: 18 Mar 2008
Posts: 41
Location: India
|
To sunshine warrior,
You are more modest in your approach, you accepted the fact that you don't seem to have enough maths to make it look absurd. If you had enough maths then you would have found it otherwise, you might have pursued further why such solutions exists, may be why it creates such solution when each starting city takes it's next city constant and look for combinations etc;. May be one can come up with some theorems or regularities in graph theory or combinations. Even I haven't gone further with this. My only objective was to prove that real mathematics requeired to decipher our environment were presented to us and there hasn't beeen any further progress and probably after Einstine we never had anyone capable enough to work to reach any further if required so.
Hope I haven't crossed the line of civility required by this forum.
Mathew Cherian |
|
| Back to top |
|
|
| sunshinewarrior |
| Posted: Thu Apr 03, 2008 11:14 am Post subject: |
|
|
Forum Ph.D.
Joined: 26 Sep 2007
Posts: 837
Location: London
|
| Mathew Cherian wrote: |
To sunshine warrior,
You are more modest in your approach, you accepted the fact that you don't seem to have enough maths to make it look absurd. If you had enough maths then you would have found it otherwise, you might have pursued further why such solutions exists, may be why it creates such solution when each starting city takes it's next city constant and look for combinations etc;. May be one can come up with some theorems or regularities in graph theory or combinations. Even I haven't gone further with this. My only objective was to prove that real mathematics requeired to decipher our environment were presented to us and there hasn't beeen any further progress and probably after Einstine we never had anyone capable enough to work to reach any further if required so.
Hope I haven't crossed the line of civility required by this forum.
Mathew Cherian |
Mathew
As far as I am aware, the P/NP problem is an important one. Since I am hampered not just by my lack of maths, but also by my lack of maths terminology (which makes me unable to pick up on some of the things you say) it was difficult for me to focus my suspicion that you may not have made the breakthrough you desire.
I wish you all the best in any case. |
|
| Back to top |
|
|
| Mathew Cherian |
| Posted: Thu Apr 03, 2008 11:21 am Post subject: |
|
|
Forum Freshman
Joined: 18 Mar 2008
Posts: 41
Location: India
|
T divided by zero,
Your question is answered as follows. NP and P are all polynomials. Then where does this polynomials appear in different algorithms or what connections has polynomials got to do with algorithms which are just menus for programing computers. It is the count of the 'comparisons' one make in the programs of a Von Nueman architecture computer. How the comparisons increase as the number of entities as reprsented by n increases. That is if a problem can varie from 1 varible to infinite variables then how does the computer respond to such increases. For example if in graph theory there are vertices called nodes and lines connecting these nodes. If there are 5 such nodes for a problem then n=5.
So the question is how the comparisons in the menu or program increase as n increase from say 5 to 10. It is noted that depending on the problem description the increase can be either linear or exponential, the comparison I mean. If it is linear it is called Polynomial Time and if exponential it is called Non deterministic polynomial time and not Non polynomial time as serpicojr explained earlier. He accepts the fact that he is not a deep master of the art of computer complexity and mistakes do happen in such times nothing to worry about.
Hope I made and attempt to lead you to understand complexity in computing.
Mathew Cherian |
|
| Back to top |
|
|
| Mathew Cherian |
| Posted: Thu Apr 03, 2008 12:16 pm Post subject: |
|
|
Forum Freshman
Joined: 18 Mar 2008
Posts: 41
Location: India
|
To Divided by zero:
By the time I thought I explained you the basics of complexity, I found that I didn't the formation of polynomials from which the name NP and P arise.
You go to my paper on http://www.npp.co.in and see under Quick sort and Bubble sort. How the polynomials get formed. Take for example Bubble sort. It is an array of [1,n] of integers. Our objective is to sort them in assenting order. You go to the nth number start comparing with the previous number and if it is lesser than the previous number you exchange their position. So the comparison is 1. Now you compare this (n-1) nubmer with (n-2) nubmer and exchange if (n-1) < (n-2). You keep on doing this by going up till you reach position one and the smallest number will be on top after n comparisons. You now go back to the bottom and repeat (n-1) times. Then (n-2) times and so on and you have the 1, 2nd, 3rd and so on nubmers. If you add up the number of comparisons it gives a series n+(n-1)+(n-2)+......+1 which is equal to n2 -(1+2+3+....+n). Like this there are n columns so you multiply the above polynomial by n. Now how much this polynomial is for n variable is or how much comparisons for n variables is got by dividing this by n which gives a polynomial with highest value as n2. So in the jargon of complexity theorists we say the algorithm for Bubble sort rise faster than n2. Why faster is again another story which is machine level work which I have explained in the positng in the psudo science section my reply to serpico jr.
Now also nn is equal to en log(n) this is an upper bound comparison and we say the algorithm rise as fast as n log(n) or and exponetial time since the e exponent or little Oh or o( n log (n)). Little o is highly complex than big Oh or O(n).
I leave it to you to find for the complexity for Quick sort. You can use my paper from the above website and you see it is O(n). Little ohs are usually intractable using conventioonal computers where as little ohs can be solved or computed using conventional computers. Little oh's are called NP's or non deterministic polynomial time algorithm Bubble sort and little ohs are called P type algorithms or computable algorithms of lower complexity like Quick sort.
Hope now you can solve any complexity problem if you know how to solve them manualy.
Mathew Cherian |
|
| Back to top |
|
|
| DivideByZero |
| Posted: Thu Apr 03, 2008 1:10 pm Post subject: |
|
|
Forum Sophomore
Joined: 02 Dec 2007
Posts: 171
|
Matthew, if you really solved the p=np question then why not submit it and make a million dollars?
btw, thanks for your clarifications! |
|
| Back to top |
|
|
| serpicojr |
| Posted: Thu Apr 03, 2008 1:58 pm Post subject: |
|
|
Forum Ph.D.
Joined: 17 Jul 2007
Posts: 871
Location: JRZ
|
| Mathew Cherian wrote: |
| We had a few conversations and I believe in one you said if you do all the routes then it is ok. Then I don't know why you feel you debunked me when my answer was yes. |
If you check every possible route, this is brute force. This is n! possibilities. n! is not polynomial time. If this (or a slight variation thereof) is your algorithm, then you didn't solve P = NP. If this is not your algorithm, please explain yourself better! The burden is on you to explain it! |
|
| Back to top |
|
|
| Mathew Cherian |
| Posted: Fri Apr 04, 2008 9:29 am Post subject: |
|
|
Forum Freshman
Joined: 18 Mar 2008
Posts: 41
Location: India
|
To Serpico jr,
First of all you notion that there are n! routes for the TSP is wrong considering the posing of the problem. First of all there is a starting city so if there is n! routes then this assumption fails. There are lesser routes may be n2 routes. Here we don't go to the starting city again which violates again the description of the problem that one should touch only a city ones. So this reduces the number of tours for a 5 city tour to just 20 < n2.
Then the algorithm is designed in such a way that just the presence of n2 doesn't make it o(n2). It is still O(n) for Quick sort. In case you need a psudo code which I developed for someone else on request I am cutting and pasting it below. It is difficult as it is for modern computer scientists, I don't know how you will cope with it. Any how try and see if you understand.
{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{
Psudo-code for the solution to NP=P
Type city[C, H, B, M, P]
Type Data
Beg_city, End_city:city
Cost: integer
Tick:Boolean
End data
Array tour_cost[1..5, 1..4] of Data
Temp:city
Start_city: city
List:city; cost, mincost:integer
Begin
Min_cost := 0
Start_city :=city[1]
Tick = false
Fill array with data
Bubble or Quick sort each column of the array in ascending order
List :=start_city; Temp:=start_city
1: Find end_city in data of the start_city
If it is ticked increment start_city to next in the column
Increment till not ticked city is reached tick it and append to the list
Start_city = end_city in data
Go to 1
Do this till all cities are reached
Add up the cost and place it in the cost
If cost < min_cost then min_cost = cost
Start_city = temp and repeat 1 again
Do this 4 times
Now after the 4th iteration increment start_city(column) and temp=start_city
Initialize data except the start_city
Repeat 1
Do complete all the tours by incrementing start_city after 4 steps
At the end data in the min_cost is the minimal cost tour.
++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Hope this suffice. I thought on your directives in finding a sort without comparison, I have found one. In simple steps it is you take the data array, subtract the first data from rest. The negative signs are clubbed together and rest discarded. Put back the first data in it’s place and do the same subtraction with the second data. You again discard the negatives. Go on like this till you get one vale which will be the Highest value. Now go back to the last but one discarded list and repeat the whole process you will get the next highest number. Keep on repeating this till you reach the first discarded list and you get a a list in ascending order.
Mathew Cherian |
|
| Back to top |
|
|
| Mathew Cherian |
| Posted: Fri Apr 04, 2008 9:35 am Post subject: |
|
|
Forum Freshman
Joined: 18 Mar 2008
Posts: 41
Location: India
|
Thank you sunshine warrior and divided by zero for your kind replies.
To divided by zero why I try to solve this problem, it is not foir the money involved in the first place. It is just to prove a point that present day knowledge of Mathematics is not limiting in explaining everything around us. Another reason it is a policy to never make anyone take easy routes out which will take humanity to dead ends. As the old saying goes 'taking easy routes makes some Trees and all Rivers crooked'.
Hope that is sufficient reason to worry about doing this problem when you can.
Mathew Cherian |
|
| Back to top |
|
|
| serpicojr |
| Posted: Fri Apr 04, 2008 10:46 am Post subject: |
|
|
Forum Ph.D.
Joined: 17 Jul 2007
Posts: 871
Location: JRZ
|
| Okay, let's suppose we have a starting city and an ending city. Then there are (n-2)! routes. You're very concerned with comparison. This is certainly an important part of the problem. Calculating the lengths of the routes is another part of the problem. Ignoring the comparisons, if you want to consider all routes, you have (n-2)! things to calculate. That's why brute force takes too long. |
|
| Back to top |
|
|
| DivideByZero |
| Posted: Fri Apr 04, 2008 1:36 pm Post subject: |
|
|
Forum Sophomore
Joined: 02 Dec 2007
Posts: 171
|
| Mathew Cherian wrote: |
Thank you sunshine warrior and divided by zero for your kind replies.
To divided by zero why I try to solve this problem, it is not foir the money involved in the first place. It is just to prove a point that present day knowledge of Mathematics is not limiting in explaining everything around us. Another reason it is a policy to never make anyone take easy routes out which will take humanity to dead ends. As the old saying goes 'taking easy routes makes some Trees and all Rivers crooked'.
Hope that is sufficient reason to worry about doing this problem when you can.
Mathew Cherian |
well if you submit your solution then you will know if it is right or wrong. |
|
| Back to top |
|
|
|
|
