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.

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.

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