P=NP - Tilted Forum Project Discussion Community

Zeraph · 06-15-2009, 11:00 AM

P = NP problem - Wikipedia, the free encyclopedia For those not familiar. Way too big of an article to quote, sorry. The math wouldn't transpose anyway.

I'm having difficulty fully understanding this, can anyone explain it in a creative way?

Is this one of those things that may never have an answer?

Jetée · 06-15-2009, 11:50 AM

From what I gather from the first paragraph, mathematicians are trying to create a basic formula that can compute a "nondeterministic algorithm" into a simple matter of equating an answer to either being "true" or "false".

No one has the answer yet, so it is reasonable and wholly factual to state that no computer can process this theory either. I'm going to study the article & links in-depth a bit later, and see if I might have come across this problem elsewhere in my random searches.

n0nsensical · 06-15-2009, 10:05 PM

In a few words P is the set of all problems for which a solution can be calculated algorithmically, NP is the set of those where that doesn't hold true. The question is if the solution to any mathematical problem can be calculated algorithmically, in which case P = NP, or if there are some problems for which no algorithmic solution exists, thus P =/= NP.

It is actually impossible to answer either way, it's simply a theoretical/philosophical question because the set of problems is infinite, and it is impossible to prove that no algorithm exists to calculate the solution to a problem and thus that a problem is in the NP set, it is only possible to prove that a P problem is such, by solving it. There are many problems for which no solution is KNOWN but it is impossible to prove that none EXISTS. The question is important most notably because a computer can calculate the answer to a P problem but cannot calculate the optimal answer to an NP problem.

Zeraph · 06-16-2009, 08:54 AM

That's basically what I got out of it. But then why does Clay Mathematics Institute - Wikipedia, the free encyclopedia have a 1million prize for a proof? Is it just publicity then?

n0nsensical · 06-16-2009, 10:21 PM

I guess the devil is in the details. I'm not even sure of all the details, I've just had a basic overview as well. So maybe there is a more formal definition that could be proven, I wouldn't really know, but at our current knowledge I'm not sure we even know one way or the other if it can be answered.

spectre · 06-17-2009, 07:20 PM

Quote:

Originally Posted by Zeraph

That's basically what I got out of it. But then why does Clay Mathematics Institute - Wikipedia, the free encyclopedia have a 1million prize for a proof? Is it just publicity then?

There are practical reasons. Think of cryptography. Factoring is a very difficult and time consuming problem (even if it doesn't seem like it) on very large numbers. If the computation of that factoring were to be done trivially, it would undermine current methods of security.

Glory's Sun · 06-18-2009, 04:36 AM

Where's Will Hunting when you need him?

Rekna · 06-19-2009, 01:58 PM

I haven't seen the correct definition here yet. The p=np problem really comes down to if a problem can be solved in polynomial time. Algorithmically speaking that means the problem can be solved in O(N^c)*, where N is the problem size and c is a constant. Some problems are believed to be NP which means they cannot be solved in O(P^c) time and instead can only be solved via brute force methods (ie trying every possible solution and seeing if it works, which I believe is O(N!). There are many classic problems that are NP and typically when you get into graph related problems NP comes up often.

An interesting fact about NP problems is that they can all be defined as a traveling salesman problem, thus if a person where to find a polynomial solution to a single NP problem then a polynomial solution would exist for all NP problems. This is where the classic problem comes in. Prove that P=NP or P!=NP.

*O(X) is known as big-O notation and it is a measure of how many operations a problem needs to be solved. If a problem were O(N) it would take on the order of N operations to solve and if it were O(N^2) it would take on the order of N^2 operations.

Zeraph · 06-30-2009, 10:48 AM

How does it follow that if I found one solution to one NP problem that it would mean all the rest follow the same logic? Really in other words, why is it we can even group all NP problems together in the first place? The dichotomy between P and NP seems arbitrary.

Rekna · 06-30-2009, 06:50 PM

From my understanding to qualify as a NP problem the problem must be rewriteable as another NP problem. Thus an equivalence class has been formed for all NP problems.

n0nsensical · 07-01-2009, 11:43 PM

Yea those would be those "details". I wouldn't even have the slightest clue how to begin proving that NP problems are equivalent for the purpose of (dis)proving that P=NP, much less proving the entire thing. I guess that may have to do with why nobody has solved it.

06-15-2009, 11:00 AM	#1 (permalink)
Zeraph Banned Location: The Cosmos	P=NP P = NP problem - Wikipedia, the free encyclopedia For those not familiar. Way too big of an article to quote, sorry. The math wouldn't transpose anyway. I'm having difficulty fully understanding this, can anyone explain it in a creative way? Is this one of those things that may never have an answer?

06-15-2009, 11:50 AM	#2 (permalink)
Jetée The Reforms Location: Rarely, if ever, here or there, but always in transition	From what I gather from the first paragraph, mathematicians are trying to create a basic formula that can compute a "nondeterministic algorithm" into a simple matter of equating an answer to either being "true" or "false". No one has the answer yet, so it is reasonable and wholly factual to state that no computer can process this theory either. I'm going to study the article & links in-depth a bit later, and see if I might have come across this problem elsewhere in my random searches. __________________ As human beings, our greatness lies not so much in being able to remake the world (that is the myth of the Atomic Age) as in being able to remake ourselves. —Mohandas K. Gandhi

06-15-2009, 10:05 PM	#3 (permalink)
n0nsensical Junkie Location: San Francisco	In a few words P is the set of all problems for which a solution can be calculated algorithmically, NP is the set of those where that doesn't hold true. The question is if the solution to any mathematical problem can be calculated algorithmically, in which case P = NP, or if there are some problems for which no algorithmic solution exists, thus P =/= NP. It is actually impossible to answer either way, it's simply a theoretical/philosophical question because the set of problems is infinite, and it is impossible to prove that no algorithm exists to calculate the solution to a problem and thus that a problem is in the NP set, it is only possible to prove that a P problem is such, by solving it. There are many problems for which no solution is KNOWN but it is impossible to prove that none EXISTS. The question is important most notably because a computer can calculate the answer to a P problem but cannot calculate the optimal answer to an NP problem. __________________ "Prohibition will work great injury to the cause of temperance. It is a species of intemperance within itself, for it goes beyond the bounds of reason in that it attempts to control a man's appetite by legislation, and makes a crime out of things that are not crimes. A Prohibition law strikes a blow at the very principles upon which our government was founded." --Abraham Lincoln Last edited by n0nsensical; 06-15-2009 at 10:17 PM..

06-16-2009, 10:21 PM	#5 (permalink)
n0nsensical Junkie Location: San Francisco	I guess the devil is in the details. I'm not even sure of all the details, I've just had a basic overview as well. So maybe there is a more formal definition that could be proven, I wouldn't really know, but at our current knowledge I'm not sure we even know one way or the other if it can be answered. __________________ "Prohibition will work great injury to the cause of temperance. It is a species of intemperance within itself, for it goes beyond the bounds of reason in that it attempts to control a man's appetite by legislation, and makes a crime out of things that are not crimes. A Prohibition law strikes a blow at the very principles upon which our government was founded." --Abraham Lincoln

07-01-2009, 11:43 PM	#11 (permalink)
n0nsensical Junkie Location: San Francisco	Yea those would be those "details". I wouldn't even have the slightest clue how to begin proving that NP problems are equivalent for the purpose of (dis)proving that P=NP, much less proving the entire thing. I guess that may have to do with why nobody has solved it. __________________ "Prohibition will work great injury to the cause of temperance. It is a species of intemperance within itself, for it goes beyond the bounds of reason in that it attempts to control a man's appetite by legislation, and makes a crime out of things that are not crimes. A Prohibition law strikes a blow at the very principles upon which our government was founded." --Abraham Lincoln

06-16-2009, 08:54 AM	#4 (permalink)
Zeraph Banned Location: The Cosmos	That's basically what I got out of it. But then why does Clay Mathematics Institute - Wikipedia, the free encyclopedia have a 1million prize for a proof? Is it just publicity then?

06-18-2009, 04:36 AM	#7 (permalink)
Glory's Sun Registered User	Where's Will Hunting when you need him?

06-19-2009, 01:58 PM	#8 (permalink)
Rekna Junkie	I haven't seen the correct definition here yet. The p=np problem really comes down to if a problem can be solved in polynomial time. Algorithmically speaking that means the problem can be solved in O(N^c), where N is the problem size and c is a constant. Some problems are believed to be NP which means they cannot be solved in O(P^c) time and instead can only be solved via brute force methods (ie trying every possible solution and seeing if it works, which I believe is O(N!). There are many classic problems that are NP and typically when you get into graph related problems NP comes up often. An interesting fact about NP problems is that they can all be defined as a traveling salesman problem, thus if a person where to find a polynomial solution to a single NP problem then a polynomial solution would exist for all NP problems. This is where the classic problem comes in. Prove that P=NP or P!=NP. O(X) is known as big-O notation and it is a measure of how many operations a problem needs to be solved. If a problem were O(N) it would take on the order of N operations to solve and if it were O(N^2) it would take on the order of N^2 operations.

06-30-2009, 10:48 AM	#9 (permalink)
Zeraph Banned Location: The Cosmos	How does it follow that if I found one solution to one NP problem that it would mean all the rest follow the same logic? Really in other words, why is it we can even group all NP problems together in the first place? The dichotomy between P and NP seems arbitrary.

06-30-2009, 06:50 PM	#10 (permalink)
Rekna Junkie	From my understanding to qualify as a NP problem the problem must be rewriteable as another NP problem. Thus an equivalence class has been formed for all NP problems.