The various “complexity classes” sort problems into something like a hierarchy: One class might contain all the problems of another, plus problems

A Short Guide to Hard Problems

submited by

Style Pass

2021-07-29 16:30:18

The various “complexity classes” sort problems into something like a hierarchy: One class might contain all the problems of another, plus problems that require additional computational resources.

How fundamentally difficult is a problem? That’s the basic task of computer scientists who hope to sort problems into what are called complexity classes. These are groups that contain all the computational problems that require less than some fixed amount of a computational resource — something like time or memory. Take a toy example featuring a large number such as 123,456,789,001. One might ask: Is this number prime, divisible only by 1 and itself? Computer scientists can solve this using fast algorithms — algorithms that don’t bog down as the number gets arbitrarily large. In our case, 123,456,789,001 is not a prime number. Then we might ask: What are its prime factors? Here no such fast algorithm exists — not unless you use a quantum computer. Therefore computer scientists believe that the two problems are in different complexity classes.

Many different complexity classes exist, though in most cases researchers haven’t been able to prove one class is categorically distinct from the others. Proving those types of categorical distinctions is among the hardest and most important open problems in the field. That’s why the new result I wrote about last month in Quanta was considered such a big deal: In a paper published at the end of May, two computer scientists proved (with a caveat) that the two complexity classes that represent quantum and classical computers really are different.