Cracking the complexity code in computer science P vs. NP problems

New research from the University of Waterloo is delving into one of the biggest questions in theoretical computer science. But the way they do that, according to doctoral student Cameron Seth, is that researchers working in the field of algorithmic approximation break down the problem into smaller parts.

“Anyone in computer science or mathematics knows about the ‘P vs. NP’ problem,” Seth says. “This is one of the infamous Millennium Prize problems. It’s so famous and so difficult that if you solve it, you’ll win a million dollars.”

To understand the crux of the “P vs. NP” problem, imagine a giant jigsaw or Sudoku puzzle. It is a “P” problem if it can be solved relatively quickly by a computer, and it is an “NP” problem if it is very difficult to solve but the solution provided can be quickly verified.

For example, a Sudoku puzzle may take a long time to solve (perhaps several hours), but once the solution is provided, it only takes a few seconds to check that all columns and rows have the correct numbers.

“In P vs. NP, the question that keeps everyone up at night is whether every quick-test solution is also a quick-fix problem. Are problems that are easy to test also easy to solve?”

The practical implications of this deep-seated problem in computer science impact important research and development in cryptography, AI, and optimization. The most common encryption methods used in sensitive networks of all kinds are based on the premise that there is a problem that is very difficult to solve but easy to verify. This is the logic underlying everything from online passwords to secure bank transfers.

Seth’s research seeks approximate solutions to problems rather than tackling them head-on.

“What I’m doing is looking at a series of smaller problems that are related to the broader P vs. NP problem. Essentially, what I’m asking is whether we can solve these other related problems,” Seth says.

For example, his recent work on graph algorithms imagines huge networks with vast numbers of connections, such as those found in large online social networking apps. Seth cuts out a small piece of the graphed network and asks what that small piece of the puzzle can tell us about the whole.

This innovation provides combinatorial tools to help solve complex optimization problems. Such tools reduce the vast number of possible combinations to a manageable subset. In this sense, Seth’s basic research is chipping away at much more difficult problems for computer science.

“What I do in my research is not exactly trying to find one solution, but to determine whether something close to a solution exists, and what that tells us about a whole set of such problems.”

The paper “A Tolerant Independent Set Tester” was presented at the 2025 Computing Theory Symposium. The findings will be published on the arXiv preprint server.