What is computational complexity theory?
Computational complexity theory is a branch of theoretical computer science. It’s main goal is to classify and compare the practical difficulty involved in solving computational problems about finite combinatorial objects.
Computational complexity theory seeks to determine the amount of resources that it will take to solve a specific problem. It also aims to explain why some problems are undecidable or intractable.
What are computational problems?
Computational problems are tasks that are solved by computers. These problems can be considered infinite collections of instances or cases along with a set of solutions (which may be empty) for every instance or case.
These problems are one of the main things studied in theoretical computer science.
The types of computational problems are:
1. Decision problems
In a decision problem, the answer for every question is either ‘yes’ or ‘no’. These problems are usually presented as the sets of all the instances for which the answer is ‘yes.’
2. Search problems
The answers in a search problem can be arbitrary strings. Search problems can be represented as search relations (relations that consist of all the instance-solution pairs).
3. Counting problems
These problems ask for the number of solutions for a particular search problem. They are represented by a function f from {0,1}* to the nonnegative integers.
4. Optimization problems
Such problems seek to find the best possible solution from the set of all the possible solutions to a search problem. These problems can be represented by their search relations.
5. Function problems
In these problems, for every input, there is a single output expected. These outputs are far more complex than the outputs for decision problems. The answer can’t just be ‘yes’ or ‘no’.
What is meant by computational complexity?
Computational complexity refers to the complexity of an algorithm. It is the amount of resources that are needed to run the algorithm and specifically focuses on time and memory requirements.
The computational complexity of a problem is essentially the complexity of the best algorithms that make it possible to solve the problem.
What are the best, worst, and average-case complexity?
These are three different ways to measure the time complexity (or any other complexity measure) of different inputs of the same size.
1. Best-case complexity
This is the complexity involved in solving a problem for the best input of size n.
2. Average-case complexity
This is the complexity involved in solving a problem on average. It is only defined regarding a probability distribution over the inputs.
3. Worst-case complexity
This is the complexity involved in solving a problem for the worst input of size n.
An amortized analysis takes the costly and the less costly operations together over the whole series of operations of the algorithm.
What are complexity classes?
Complexity classes are sets of problems of related complexity. Simple complexity classes are defined by the type of computational problem, the model of computation, and The resource or resources that are being bounded, and the bound.
To see how complexity classes are defined, here is the definition for the complexity class DTIME(f(n)).
The set of decision problems that can be solved using a deterministic Turing machine within time f(n).
Essentially, complexity classes are utilized to group together problems that need similar amounts of resources to be solved. As an example, the group of problems that can be solved in polynomial time are considered a part of the class P. Another example is that the group of problems that take an exponential amount of space are in the class EXPSPACE.
There also are some classes which are contained within other classes. For example, if it is possible for a problem to be solved in polynomial time, it is definitely possible for that problem to be solved in exponential time as well.
Why is computational complexity theory important?
Computational complexity theory is a vital topic in theoretical computer science. It has direct applications to computability theory and makes use of computation models like Turing machines to assist in testing complexity.
One of the reasons why computational complexity theory is important is that it aids computer scientists in relating and grouping problems together into complexity classes. Sometimes, if you can solve one problem in a complexity class, you can find a way to solve other problems in its complexity class as well.
Computational complexity also assists in determining the difficulty of a problem, which is usually measured in terms of the amount of time and space (memory) that it takes to solve a specific problem. As an example, some problems can be solved in polynomial amounts of time and others take exponential amounts of time, with respect to the input size.
There are quite a few real-world implications for computational complexity theory, especially in algorithm design and analysis. You can analyze an algorithm in terms of its complexity, and this is usually described in big-O notation.
Programmers tend to want to write efficient algorithms. The ability to see whether an algorithm runs in polynomial time versus exponential time can inform a programmers whether their algorithm is the best choice or not.
Computational complexity even has applications for biologists who study neurons, electrical engineers who design hardware, linguists who study languages and grammars, and physicists who are building quantum computers.
Essentially, computational complexity theory is rather important because both in theory as well as in practice, it helps computer scientists understand the limits of what computers can do and what they cannot do.
In several cases, it is possible to model problems as decision problems - problems that can be answered with either a “yes” or a “no.” If you want examples of decision problems, consider the travelling salesperson problem, 3SAT, and primality testing. It is possible to simulate decision problems on computational models like Turing machines.
