Computational complexity

Authors: Steve Bentioulis, Augie Bravo, Will Murphy

Introduction

“The subject of my talk is perhaps most directly indicated by simply asking two questions: first, is it harder to multiply than to add? and second, why?...there is no algorithm for multiplication computationally as simple as that for addition, and this proves something of a stumbling block” - Alan Cobham, 1965

Computational complexity refers to the amount of resources needed to solve a problem. Complexity increases as the amount of resources required increases.

While this notion may seem straightforward enough, the notion of computational complexity has profound impacts. Additionally, the theory of computational complexity is in its infancy as it has only been studied in earnest starting in the 20th century.

Theory, Methodology

The concept of computation has evolved since the advent of the standard universal electronic computer and it’s widespread societal adoption. And while the electronic computer is based on the refined definition of computation, it’s important to remember that computation is a major scientific concept in it’s own right.

When studying computation, a key area of interest is understanding what problems are, in fact, computable. Researchers have shown that some tasks are inherently incomputable in that no computer can solve them without going into infinite loops on certain inputs. This phenomena begs the question how do you determine if a problem can be computed, and moreover, for those problems that can be computed how can you calculate the complexity associated with computing the answer.

The focus of computational complexity is the measure of computational efficiency quantifying the amount of computational resources required to solve a problem.

Complexity Class

Within the study of computational complexity there exists the notion of a complexity class defined as a set of functions that can be computed within given resource bounds.

P

Class P Computational complexity problems refer to those that can solved in polynomial running time, where “P” stands for polynomial. Important to note that class P only includes specific decision problems, e.g. product of 3 and 5; its is not acceptable to state that integer multiplication is in class P. Also, running time is a function of the number of bits in the input

NP

NP stands for nondeterministic polynomial time, originally referring to nondeterministic Turing machines (NDTM) in which the Turing machine has two transition functions and the computer arbitrarily determines which transition function to apply.

Complexity class NP consists of problems that can be verified within a running time upper bounded by polynomial function. Verifiability is the concept that if given a potential solution to the problem it can be confirmed or rejected.

NP-hard

The NP-hard complexity class is a subcategory of the NP complexity class that defines those problems that are at least as hard as any other language in NP. If P ≠ NP, then NP-hard problems cannot be decided in polynomial time. See P vs NP on this page.

NP-complete

NP-complete refers to those problems within the NP complexity-class that are the hardest problems t solve within the NP class. Examples of NP-complete problems include Independent Set, Traveling Salesperson, Subset Sum, and Integer Programming problem. The implication of these problems is that they are not in P unless P = NP.

P vs NP

The difference between class P and class NP computational complexity is illustrated simply with a crossword, sudoku, or another puzzle type. The effort required to solve a puzzle from scratch would be categorized as class P complexity, whereas the effort required to verify a friend’s solution to a sudoku puzzle would be classified as a class NP complexity.

This then begs the question that for every class NP problem, i.e. those that can be verified, does that mean it can also be solved? If so, then P = NP. However, we have not yet been able to prove that P = NP and thus the implications that P ≠ NP must also be considered.

The importance of understanding P vs NP is the subject of much discussion and has even sparked competition in the scientific community. The problem of P vs NP was selected by the Clay Mathematics Institute (CMI) of Cambridge, Massachusetts as one of seven most difficult and important problems to be solved at the dawn of the 21^st century. A prize of $1 million has been allocated for anyone that can bring forward a solution

Conclusion

Computational complexity has important implications in the field of computer science and far reaching applications that span numerous fields and industries. As computable problems become more complex the ability to increase the efficiency in which they are solved becomes more important. Advancements toward solving P vs NP will have far reaching impacts on how we approach the computability of problems and the ability to efficiently allocate resources.

Sources

1. A. Cobham, The intrinsic computational difficulty of functions, in Y. Bar-Hillel, ed., Logic, Methodology and Philosophy of Science: Proceedings of the 1964 International Congress, North-Holland Publishing Company, Amsterdam, 1965, pp. 24-30
2. Arora, S., & Barak, B. (2009). Computational complexity: a modern approach. Cambridge: Cambridge University Press. Retrieved from https://cornell-library.skillport.com/skillportfe/main.action?path=summary/BOOKS/31235
3. Du, D., & Ko, K.-I. (2014). Theory of computational complexity. (Second edition.). Hoboken, New Jersey: Wiley. Retrieved from http://onlinelibrary.wiley.com/book/10.1002/9781118595091
4. Clay Mathematics Institute, The Millennium Prize Problems. Retrieved from http://https://www.claymath.org/millennium-problems/millennium-prize-problems