The Problem with Problems
In 1971, a computer-scientist by the name of Stephen Cook proposed a profound theoretical problem. This problem was so profound that it was selected as one of the 7 Millennium Prize Problems :
The P versus NP Problem
What is the P vs NP problem?
Essentially this is a problem about solving problems. In his proposal, Cook described classes of problems which centered around the Turing Machine as the standard for computation:
P( for polynomial time) and NP (for nondeterministic polynomial time).
Cook describes the P class as “…the class of decision problems solvable by some algorithm within a number of steps bounded by some fixed polynomial in the length of the input.” (Stephen Cook)
In other words these are problems that a deterministic Turing machine can solve within a “reasonable” amount of time. “Reasonable” meaning that the execution time of the algorithm that was used to solve a problem would be measured within polynomial time (See: Time Complexity). Examples within this realm would include performing simple mathematical operations to slightly more complex problems like the Sum of Fibonacci Numbers Function or finding all the odd factors of a smaller number.
When discussing the NP class Cook explains that “[the] notation NP stands for “nondeterministic polynomial time”, since originally NP was defined in terms of nondeterministic Turing machines (that is, machines that have more than one possible move from a given configuration)….”(He goes on to explain in further and complex detail :here). Problems that are part of the NP class are computational decision problems that are easily checked but would require more complex steps in order to be solved. (Note: This is a simplification of the NP class. I would highly recommend researching further on the topic of nondeterministic Turing machines to get a better sense for how this computing process works.)
NP-complete and NP-Hard
NP-complete problems are easily checked but there is not a known way to quickly solve them.
NP-Hard class is described as “at least as hard as the hardest problems in NP”.
Examples:
NP-complete Examples
NP-hard
(*Note: Some problems, when set under certain parameters can be considered either NP-hard or NP-complete)
Let’s go back to the original problem: P = NP?
The picture above diagrams two differing view points. As of now, we generally operate under the general assumption that there is this gradience in the complexity of problems, that P ≠ NP even though this has not been formally proven . What would it mean if P=NP? In simple terms, this would mean that the problems we perceive as being complex in nature and scope would actually be readily solvable and they could even be as solvable as a P class problem. Some consider this within the realm of possibility because our standards of computing are becoming more advanced. (See: Quantum Computing)
What are the implications here?
One immediate example is in the realm of cryptography. Cryptography relies heavily on the notion that certain codes are “unsolvable” however if P =NP were proven to be true, this would shake the foundations of cryptography because this would mean all the methods that we rely on for making things “secure” would actually be insecure and readily solvable.
There are other implications which go beyond the realm of computing which I encourage you to look into.
Side Thought:
As we are learning to become developers, we face many problems that we attempt to solve. Understanding the nature and scope of any given problem is important to figuring out the best approach for how to reach a desired solution. If we have a particular goal in mind and we reach a problem where the nature is too complex and/or the scope is too wide, we may come to the conclusion that a particular problem may not be worth solving.
After wrestling with trying to understand P vs. NP, I and others can be assured that most of the problems that we will encounter as developers will most likely be able to be solved within a practical amount of time. However if we do encounter and recognize such a complex problem, it might be best to walk away. Although in the process of trying to solve a such a problem may lead you to discover something new.
Suggested Reading:
