Brief guide to complex computational problems

What computer is easy to make, and that is almost impossible? These questions underlie the issue of computational complexity. We present you a map of this landscape.

Different complexity classes sort tasks hierarchically. One class can contain all the tasks of another, plus tasks requiring additional computational resources.

What is the fundamental complexity of the task? Such is the formulation of the basic task of computer scientists trying to sort tasks by so-called. complexity classes . These are groups containing all computational tasks that require no more than a fixed amount of computational resources, such as time or memory. Take a simple example with a large number of types 123 456 789 001. You can ask the question: is it a prime number - one that is divisible only by 1 and itself? Informatics specialists can answer it with the help of fast algorithms - such that they do not begin to slow down on 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 fast algorithm to answer it - only if you use a quantum computer. Therefore, specialists in computer science believe that these two tasks belong to different classes of complexity.

There are many different classes of difficulty, although in most cases the researchers could not 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 subtle or obvious, and it is quite difficult to understand all classes well. Therefore, we have compiled this guide to the seven most fundamental classes of complexity. And you will no longer confuse BPP and BQP.
')

P

Indicates : polynomial time

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

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

Typical tasks :

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

What the researchers would like to know : does P match NP? The coincidence would make a revolution in computer science and deprive most of the cryptographic systems of meaning (but almost no one believes this).

NP

Indicates : nondeterministic polynomial time

Short Description : all tasks that a classic computer can easily check with a solution.

Exact description : the problem falls into NP class, when there is a brief proof of the correctness of the answer if there is a yes answer. If the input data is a string X, and you need to decide whether the answer is “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 the “brief witness” - all NP tasks have short witnesses, thanks to which they can be checked).

Typical tasks :

• The task of the click . Imagine a graph with edges and vertices — for example, vertices represent users of a social network, and an edge means that they are “friends.” A clique is a subset of this graph in which all people are friends with 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 click is an NP-complete problem , 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 — check it easily.
• Salesman task . Given a set of cities with distances between any two pairs - is there a way to drive around all the cities, driving less than a certain distance? For example, can a traveling salesman drive around all the capitals of the US states, having traveled less than 11,000 miles?

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

PH

Indicates : polynomial hierarchy

Short description : PH is a generalization of NP. It contains all the tasks you can get by starting with a task from NP, and imposing additional levels of difficulty.

The exact description : PH contains tasks with a number of different “quantifiers” that complicate these tasks. Example of a problem with different quantifiers: If we are given X, is there such a Y such that for each Z there is a W for which R is fulfilled? The more in the quantifier problem, the more complicated it is, and the higher the polynomial hierarchy.

A typical task is to determine whether a click of size 50 really exists and there is no click of size 51.

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

Pspace

Indicates : polynomial space constraint

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

Exact description : When solving PSPACE tasks, you are no longer worried about the time, you are worried only about the amount of memory that is required for the operation of the algorithm. Computer scientists have proven that PSPACE contains PH, which contains NP, which contains P.

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

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

BQP

Indicates : quantum polynomial time with limited error probability

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

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

A typical task : to find the prime factors of an integer.

What the 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 NP contains BQP, but they believe that these two classes cannot be compared - there are tasks included in NP, but not included in the BQP, and vice versa.

EXPTIME

Indicates : exponential time

Short Description : all tasks that can be solved in exponential time on a classic computer.

Exact description : EXP contains all previous classes - P, NP, PH, PSPACE and BQP. The researchers proved that it is different from P - they found problems included in EXP and not included in P.

A typical task : generalization of games like chess and checkers. If the chessboard can be of any size, then the task of determining whether one of the players has an advantage becomes an EXP task.

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

BPP

Indicates : polynomial time with limited error probability

Short description : Tasks that can be solved quickly with the help of algorithms that use randomness.

Exact description : BPP coincides with P, with the difference that the algorithm may include steps in which decision making occurs by chance. Algorithms in BPP need to give the correct answers with a probability close to 1.

A typical problem : you have two different formulas that give polynomials with many variables. Do these formulas compute the same polynomial? This is the task of verifying polynomial identity.

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