Tilted Forum Project Discussion Community - View Single Post

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.

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.