Tilted Forum Project Discussion Community - View Single Post

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.

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