Cracking the code of complexity
Research from the Cheriton School of Computer Science is making inroads on one of the biggest problems in theoretical computer science. But the way to do it, according to Cameron Seth, a PhD candidate working in the field of algorithmic approximation, is by breaking the problem down into smaller pieces.
“Everyone working in computer science and mathematics knows about the ‘P vs. NP’ problem,” Cameron says. “It’s one of the notorious Millennium Prize Problems: so famous and so difficult that solving one will earn you a million dollars.”
To understand the crux of the “P vs. NP” problem, imagine an enormous jigsaw puzzle or a Sudoku puzzle. It would be a ‘P’ problem if it could be solved relatively quickly by a computer, whereas they would be an ‘NP’ problem if they were extremely difficult to solve, but a provided solution could be quickly verified.
For example, a Sudoku puzzle might take someone a long time to solve — perhaps hours — but once a solution is provided, it takes only seconds to check that all the columns and rows have the right numbers. “With P vs. NP the question that’s keeping everyone up at night is whether every solution that can be checked quickly is also a problem that can be solved quickly. Is every problem that’s easy to verify also easy to solve?”
Cameron Seth is a fourth-year PhD student in the Algorithms and Complexity Group at the Cheriton School of Computer Science at the University of Waterloo, supervised by Professor Eric Blais.
He is generally interested in graph algorithms, and in particular sublinear-time and approximation algorithms. Recently, he has been studying a new application of the graph container method to property testing in the dense graph model.