Quick Computing Tutorial

What is easy for a computer to do and what is almost impossible? These questions are at the heart of the issue of computational complexity. We present you a map of this landscape.

Different complexity classes sort tasks in a hierarchical form. One class can contain all the tasks of another, plus tasks that require additional computing resources.

What is the fundamental difficulty of the task? This is the formulation of the basic task of computer scientists who are trying to sort the tasks according to the so-called. difficulty classes. These are groups containing all computational tasks that require no more than a fixed amount of computational resources - such as time or memory. Let's take a simple example with a large number like 123 456 789 001. One may ask: is it a prime number - one that divides only by 1 and itself? Computer scientists can answer it with fast algorithms - such that they do not start to slow down at arbitrarily large numbers. In our case, it turns out that this number is not prime. Then we can ask the question: what are its prime factors? But there is no quick algorithm to answer it - only if you use a quantum computer. Therefore, computer scientists believe that these two tasks belong to different complexity classes.

There are many different classes of difficulty, although in most cases the researchers were unable to prove that one class is clearly different from the others. Evidence of differences between classes is one of the most difficult and important tasks in this area.

The difference between classes can be barely distinguishable or obvious, and it is quite difficult to understand all classes well. Therefore, we have compiled this guide to the seven most fundamental difficulty classes. And yes, you will no longer confuse BPP and BQP.

P

Denotes : polynomial time

Short description : all tasks that a classical (non-quantum) computer can easily solve.

Exact description : class P algorithms should stop working and give the correct answer no more than in time n ^c , where n is the length of the input data, c is a constant.

Typical Tasks :

• Is the number prime?
• What is the shortest path between two points?

What researchers would like to know : Does P coincide with NP? Coincidence would revolutionize computer science and make most of the cryptographic systems meaningless (but almost no one believes this).

NP

Denotes : non-deterministic polynomial time

Short description : all tasks that a classic computer can easily check if there is a solution.

Exact description : the problem falls into the class NP when, if the answer is yes, there is a short proof of the correctness of the answer. If the input is a string X, and you need to decide whether the answer matches “yes”, then a brief proof will be another string, Y, which can be used to check the correctness of the answer “yes” in polynomial time. (Y is sometimes called a “short witness” - all tasks from NP have short witnesses, thanks to which they can be checked).

Typical Tasks :

• The task of clicking . Imagine a graph with edges and vertices - for example, the vertices indicate users of the social network, and the edge means that they are “friends”. A clique is a subset of this graph in which all people are friends of each other. You can ask the following questions about the graph: is there a click of 20 people in it? 50 people? 100? Finding a clique is an NP-complete task , that is, its complexity is the highest of all NP-tasks. But, having a potential answer - a subset of 50 nodes that may or may not be a click - is easy to verify.
• The task of the salesman . Given a set of cities with distances between any two pairs - is there a way to go around all the cities, driving less than a certain distance? For example, can a salesman travel all US capitals with less than 11,000 miles?

What researchers would like to know: P = NP? Specialists in computer science and did not come close to solving this problem.

PH

Denotes : polynomial hierarchy

Short Description : PH is a generalization of NP. It contains all the tasks that can be obtained by starting with a task from NP, and imposing additional levels of difficulty.

Exact description : PH contains tasks with a number of different “quantifiers” that complicate these tasks. An example of a problem with different quantifiers: If we are given X, does there exist Y such that for every Z there exists W for which R is satisfied? The more quantifiers in the problem, the more complicated it is, and the higher the polynomial hierarchy.

A typical task is to determine if there really is a clique of size 50, and there is no clique of size 51.

What researchers would like to know: no one has yet been able to prove that PH is different from P. This problem is equivalent to the equality of P and NP, because if it suddenly turns out that P = NP, then all PHs will be reduced to P (P = PH).

PSPACE

Denotes : polynomial space limitation

Short description : PSPACE contains all the tasks that can be solved using a reasonable amount of memory.

Exact description : When solving PSPACE tasks, you no longer worry about the time, you worry only about the amount of memory that is required for the algorithm to work. Computer scientists have proven that PSPACE contains a PH that contains an NP that contains P.

A typical task : all tasks from P, NP, and PH are contained in PSPACE.

What researchers would like to know : Is PSPACE different from P?

Bqp

Designates : quantum-polynomial time with error probability limitation

Short description : all tasks that can be easily solved on a quantum computer.

Exact description : all the tasks that can be solved on a quantum computer in polynomial time.

Typical problem : find prime factors of an integer.

What researchers would like to know : So far, it has been proven that BQP is contained in PSPACE, and that BQP contains P. Researchers do not know whether BQP is contained in NP, but they believe that these two classes cannot be compared - there are tasks that are part of NP, but not in BQP, and vice versa.

EXPTIME

Denotes : exponential time

Short description : all tasks that can be solved in exponential time on a classical computer.

Exact description : EXP contains all the previous classes - P, NP, PH, PSPACE and BQP. Researchers proved that it is different from P - they found tasks that are part of EXP and not part of P.

Typical task : generalization of games such as chess and checkers. If a chessboard can be of any size, then the task of determining whether one of the players has an advantage becomes the task of EXP.

What researchers would like to know: they would like to prove that PSPACE does not contain EXP. They believe that there are tasks that are part of EXP but not part of PSPACE, because sometimes it takes a lot of time to solve a task from EXP. Researchers know how to separate EXP and P.

BPP

Denotes : polynomial time with error probability limited

Brief description : tasks that can be quickly solved using random algorithms.

Exact description : BPP is the same as P, with the difference that the algorithm may include steps in which decisions are made randomly. Algorithms in BPP need to give the correct answers with a probability close to 1.

Typical task : you have two different formulas that produce polynomials with many variables. Do these formulas calculate the same polynomial? This is the task of checking polynomial identity.

What researchers would like to know: Are BPP and P equal? ​​If they are equal, then any algorithm with randomness could be eliminated from randomness. They believe that it is - that for every problem for which there is an effective random algorithm, there is an effective deterministic algorithm - but they have not yet been able to prove this.