Get Quartz in your inbox

Free daily briefing on global business news.

10 unsolved problems in computer science, explained

These 10 unsolved problems in computer science, from P versus NP to quantum advantage, bear on cryptography, algorithm design and computing's limits — here is what each asks

The encryption that protects a bank login rests on an unproven assumption. Nobody has shown that the math behind it is hard to break. Delivery routing, scheduling and circuit verification face a similar gap: the best methods anyone has found may or may not be the best possible. Computer scientists call these gaps open problems. The best known, P versus NP, has stood unresolved since Stephen Cook formalized it in 1971.

Most of these questions belong to computational complexity, the branch of computer science that asks how much time, memory or other resources a problem needs. The field measures difficulty by how the work grows as the input gets larger. An algorithm counts as efficient when its running time is polynomial. That means the work grows no faster than the input size raised to a fixed power, such as n squared or n cubed.

That distinction sounds abstract, but it decides what is feasible. A problem solvable in polynomial time can usually be handled at scale. A problem that appears to need exponential time can stall the fastest hardware on inputs of modest size. Each extra element in the input can double the work. Security systems and logistics software both depend on which side of that line certain problems fall.

This list covers 10 unsolved problems in computer science, a selection rather than a complete or ranked inventory. Several sit at the center of complexity theory, including P versus NP and the question of how complexity classes relate to one another. Others connect directly to cryptography, such as whether one-way functions exist and whether integer factoring has a fast classical algorithm. Some concern specific algorithms, like the true cost of multiplying matrices or deciding whether two graphs are structurally the same. The last asks whether quantum computers can efficiently solve problems that classical machines cannot.

Each slide explains what the problem asks, what has been established and what remains open. One carries a formal bounty: P versus NP is one of seven Millennium Prize Problems the Clay Mathematics Institute named in 2000, each with $1 million attached. Others are known mainly inside the field but shape how algorithms are designed and how security is engineered. Each entry stands on its own, so a reader can start anywhere.

P versus NP: can every quickly checked problem be quickly solved

P versus NP asks whether every problem whose solution a computer can check quickly can also be solved quickly. No one has proved the answer either way.

The two labels name classes of problems. P covers problems a computer can solve in polynomial time. NP covers problems where a proposed answer can be verified in polynomial time, even if finding that answer seems to take far more work.

The traveling salesman problem shows the gap. Take a list of cities and the distances between them. Is there a route that visits each city once and stays under a set total length? Checking a proposed route only means confirming it visits every city once and adding up its legs. No known algorithm finds such a route in polynomial time for every possible list of cities.

Stephen Cook formalized the question in 1971, and Leonid Levin independently reached related results. Their work showed that Boolean satisfiability, known as SAT, is NP-complete. SAT asks whether the variables in a logical formula can be set to true or false so the whole formula comes out true.

NP-complete problems are the hardest problems in NP. Any problem in NP can be translated into an NP-complete problem with only polynomial extra work. A fast algorithm for a single NP-complete problem would therefore give fast algorithms for everything in NP.

Richard Karp's 1972 paper listed 21 NP-complete problems. That list showed NP-completeness was not a quirk of formal logic. It reached problems about networks, packing and scheduling. The traveling salesman problem, in its yes-or-no form, belongs to the same family.

The Clay Mathematics Institute added P versus NP to its Millennium Prize Problems in 2000. A correct solution would earn the institute's prize money.

Each possible answer carries a precise consequence. A proof that P equals NP would mean SAT, the traveling salesman decision problem and every other NP-complete problem have a polynomial-time algorithm. A proof that P does not equal NP would confirm that no NP-complete problem can be solved in polynomial time.

A polynomial-time algorithm is not automatically a practical one. A running time that grows with the input size raised to the 100th power still counts as polynomial. Such an algorithm would settle the theory without making hard problems easy to solve on real machines.

NP versus co-NP and verifying no-answers quickly

NP versus co-NP asks whether every problem with quickly checkable yes-answers also has quickly checkable no-answers. The question remains open. Its answer would show whether proofs that something is impossible can always be as short and easy to check as proofs that it is possible.

The class NP is defined by verification. A problem belongs to NP if every yes-answer comes with a short piece of evidence that a computer can check in polynomial time. For Boolean satisfiability, that evidence is a list of true-or-false values that makes the formula come out true.

co-NP flips the direction. It contains the problems whose no-answers can be verified quickly. Put another way, a problem is in co-NP when its complement is in NP.

The gap between the two shows up clearly in logic. Showing that a formula can be satisfied takes one working assignment. Showing that it can never be satisfied appears to require ruling out every assignment. No general shortcut for doing that is known.

Tautology checking is the standard example. A tautology is a formula that is true under every possible assignment of its variables. Deciding whether a formula is a tautology is co-NP-complete. That means every other problem in co-NP can be translated into it efficiently.

The brute-force approach does not scale. Each added variable doubles the number of assignments to test. A formula with 30 variables already has more than a billion possible combinations.

The question connects directly to P versus NP. If P equals NP, then NP equals co-NP. The link comes from a property of P: flipping the yes-or-no output of a polynomial-time algorithm still gives a polynomial-time algorithm. The complement of every problem in P therefore stays in P. The reverse implication........

© Quartz