I got NP problems, but P ‘aint one.
Do all the questions that can be asked, have solutions, and if so can one find those solutions efficiently and check whether they are correct? This question is summed up in the problem of P vs NP, which is a very important unsolved $1 million question in mathematics and computer science, and an answer to this problem may well have vast consequences on everyday life.
Understanding P vs NP
To understand the problem of P vs NP, one must first understand some the basic concepts in computer science like algorithms, that are defined as “A procedure that produces the answer to a question or the solution to a problem in a finite number of steps (Merriam-Webster, 2012).” The complexity of a given algorithm can be simply be defined as the number of steps required for a given input. The relationship between the input size and the number steps is called the computational complexity (Sleator, 2010) often represented in Big O notation.
The computational complexity of the Grade School Addition Algorithm (what you would use to add numbers with a pen and paper) is of complexity O(n) (Sleator, 2010). Which means the number of steps required, n, to complete the algorithm increases linearly with the ‘size of the problem’ or more formally the number of bits (0s and 1s) to specify the input of the problem (Choueiry, 2006). Expanding on this idea, an algorithm of complexity O(n²) (Vernon, 2005), means the number of steps will increase quadratically (to the power 2) with the size of the problem. That is, if the size of the problem was say 3, the number of steps to complete the O(n²) algorithm that solves this question is (asymptotically) 3² or 9 steps.
Assuming that each of the steps takes the same interval of time to compute then the computational complexity can be described as the time to complete the algorithm with respect to the input size (Choueiry, 2006). Therefore the complexities above can be generalised for an algorithm of complexity O(nk), for any constant number k, will take polynomial time to complete (Terr, 2012). Namely when k = 1 is linear time and k = 2 is quadratic time.
An algorithm can also take exponential time to compute, in Big O notation this would be O(bn), where b is any integer. For the case b = 2, simply increasing the input size, n, by 1 will double the required computation time.
An algorithm is considered efficient if the complexity of the algorithm is the lowest degree it can be, i.e., the best algorithm possible, and solves the problem in a time interval that is deemed acceptable for the task (Rinker, 2002).
What is P?
P is defined informally as the set of all the problems that we can solve ‘easily’. Meaning an efficient algorithm exists to solve the problem that can be implemented on (perhaps) a computer, i.e. the set of problems that can be solved in polynomial time (Widgerson, 2012).
Solutions to problems in the set P can be found directly with an algorithm within a number of finite steps, therefore the solution does not require searching for the answer (Sipser, 2006). For example, consider a multiplication problem. Given the pair of numbers 3 and 4, what is product of these numbers? 12. With a multiplication table (like the ones on the back of your maths ex exercise book) a solution can be found via searching, but in general this is not the most efficient method (Sleator, 2010) to solve the problem. Instead a more (but not most) efficient method is to use the Grade School Multiplication Algorithm (what you would use to do multiplication with pen and paper) that has complexity O(n²). The algorithm requires no searching and will arrive at the solution (of 12) in polynomial time (Sleator, 2010).
What is NP?
Conversely NP is defined informally as the set of all the problems that can potentially be solved, but are ‘hard’ to solve. Meaning no efficient algorithm exists to solve the problem, in any acceptable time period. These problems can not be solved in polynomial time, but rather in non-polynomial time (i.e., exponential time) (Widgerson, 2012).
An example of a NP problem is the inverse of the above multiplication problem. Given the product 12, what are the factors that make up 12? 3 and 4. This type of problem is called Integer Factorisation (an integer is a whole number) (Barnes, 2004) and is an NP problem (Sipser, 2006) as the only way to find a (non-trivial) solution, that is 3 and 4 (or 6 and 2), is to start with the product, 12, and divide by all the numbers from 1 to 12, and test if one of those numbers divides evenly. The end result is that 3 and 4 (along with 6 and 2) are factors of 12. The solution of 12 and 1 is called a trivial solution as it’s result is nothing special. This method is very slow however, in fact takes exponential time, O(10^(n/2)) (Sleator, 2010), to solve. These types of problems are often be called searching problems (Sipser, 2006), because as one can guess searching is required to find the solution. Searching is not favourable and is considered ‘hard’ and very time consuming. Problems in NP have the property that once a solution is found, it can be checked easily (Sipser, 2006). Given the possible solutions 3 and 4 from your algorithm, the authenticity of such solutions can be verified easily, simply by multiplying 3 and 4 and checking it against 12. Recall that multiplication exists in P, which means to check this problem is ‘easy’.
Defining P vs NP
The two classes of problems P and NP can be simply summed up as; P problems are problems that are ‘easy’, require no searching, and can be checked ‘easily’. While NP problems are problems that are ‘hard’, require searching to find the solution but checking it is ‘easy’.
The problem of P vs NP simply asks, can searching problems be solved without searching (Sipser, 2006)?
Deterministic and Nondeterministic Turing Machines
By convention Turing machines are used to benchmark these problems. There are two types of Turing machines, a deterministic Turing machine, that can only complete one step or computation, at a time (Cunningham, 2011). A common computer is an example of such a machine (Candrakova & Dunik, 2010). The other type of Turing machine is naturally a nondeterministic Turing machine, that at any step in the algorithm it can split off and perform more than one computation simultaneously. A nondeterministic Turing machine can split into branches at any and every step, each branch is a new computation, therefore it can solve a very large number of sub-problems concurrently (Cunningham, 2011). Multithreading in CPUs is an example of a nondeterministic Turing machine. However true infinitely nondeterministic Turing machines do not exist in practice, but are instead only a theoretical construct.
Redefining P as the set of all problems that can be solved in polynomial time with an algorithm on a deterministic Turing machine and NP as the set of all problems that can only be solved in polynomial time with an algorithm on a nondeterministic Turing machine.
One can easily see that P must be contained in the set NP (P ⊂ NP) (Cunningham, 2011) (think Venn Diagrams). A nondeterministic Turing machine can act as deterministic Turing machine by not splitting and branching off at any steps in the algorithm. Therefore all P problems can be solved in polynomial time on deterministic and nondeterministic Turing machines. The converse is not true, a deterministic Turing machine cannot emulate a nondeterministic Turing machine (in general). Meaning NP problems can not be solved in polynomial time on a deterministic Turing machine.
More on P vs NP
This poses the question is P equal to NP? The answer to this problem is currently unsolved and is one of the Millennium Prizes offered by the Clay Institute for Mathematics for which the award for proving or disproving this statement is a cash prize of $1 million (Cook, 2000). A proof or otherwise will have vast implications in many fields of study and will eventually (or perhaps immediately) trickle down to every day lives of people around the world.
If the outcome was that P equal NP it would mean that for any problem that can be solved in polynomial time on a nondeterministic Turing machine there would also exists an algorithm that can arrive at the same result on a deterministic machine. Therefore all the ‘hard’ problems that can not be currently solved in polynomial time, can now be solved and now become ‘easy’ (Kazad, 2003). Which is a big problem for the technologically savvy world, as the security of modern cryptography relies on the conjecture being false and P not equal NP (Wigderson, 2012).
NP-Completeness
Inside the set of NP problems there exists a set of problems classified as NP-complete. NP-complete problems have the attribute that if an efficient solution to one of the problems is found, this implies immediately that there is an efficient solution to all of the other problems contained in NP (Wigderson, 2012). To prove that P equal NP only one efficient algorithm (or proof) of a NP-complete problem that can be solved in polynomial time on a deterministic Turing machine is needed (Wigderson, 2012). There are thousands of known problems that lie in the NP-complete set. An algorithm to any NP-complete problem can be transformed to solve any other problem in NP (Sipser, 2006). The converse is not true, an efficient solution to a problem only contained in NP does not imply that P equal NP, only those that are also NP-complete does this property hold (P ⊂ NP-complete ⊂ NP) (Wigderson, 2012).
Implications of P = NP and P ≠ NP
Say an efficient solution to a NP-complete problem is found. What does this mean, and what impact will it have? The modern world relies heavily on the assumption that P not equal NP, that there exists problems that are ‘hard’ to solve. This assumption allows the use of very large numbers (thousands of bits) that are the product of two prime numbers to be used for encryption purposes (Sipser, 2006). The encryption works because finding those two prime factors is ‘really hard’ (and gets exponentially harder with larger and larger numbers), thus breaking or cracking the encryption is ‘very hard’. This fact makes transferring valuable information such as credit card details and passwords very secure, if they are encrypted with this method. As the problem of Integer Factorisation is contained in NP, if an efficient solution to a NP-complete problem is found then that solution can be ‘transformed’ into a solution to solve Integer Factorisation (Eppstien, 2000). Therefore Integer Factorisation will become an easy problem to solve, and worse can be done in polynomial time. Which would allow devious people to find the two prime factors used in the encryption process, and follows the secure nature of our world is broken and credit card information and passwords can be stolen with ease.
Another consequence of this result is that the solution to all the problems in NP will become trivial. This essentially means the human creativity needed to solve these problems by any method (including searching) can be done with a computer. “Creativity will become automated (Sipser, 2006)”.
Conversely if it is proved that P not equal NP then this means there are certain problems, namely NP problems, that cannot be solved ‘easily’ (Wigderson, 2012). There is a limit to human knowledge. That at best these problems can only be solved by searching for the solution. This is widely regarded to be the case (Sipser, 2006), but is not known for sure as no such proof has been found.
Conclusion
A proof for P equal NP or P not equal NP will have vast consequences on the world and change the way new problems are tackled. Whether it be the downfall of the encryption services and the rise of a utopian world with infinitely, easily, automated and solvable problems. Or the undeniable confirmation of the secure modern world, still with the reliance on creative thought to solve ‘hard’ problems, and the acceptance of that fact that not all problems can be solved ‘easily’ and human knowledge is finite. Or maybe it will remain unproven and the security of the world’s banking information will still rely on a ‘hunch’.
Author’s Note
This article was originally written as an undergraduate academic essay for the School of Computer Science at the University of Adelaide. A complete reference list can be found here.
