“I find the idea of showing impossibility really intriguing”

Tenure Track Assistant Professor, Mika Göös, who heads the Theory of Computation Laboratory 5 is working on a big problem. It’s so big that, along with many of our planet’s brightest minds, he doesn’t really believe it will be solved within his lifetime. But this isn’t stopping him from trying!

“The biggest open problem in complexity theory is P versus NP. It’s one of the seven Millennium problems that each carry a one-million-dollar prize for solving them. P versus NP is the only problem at the intersection of computer science and mathematics and nobody really has any clue how to attack it directly,” says Göös.

P versus NP asks the question as to whether a problem for which it’s possible to verify a solution fast is also a problem for which one can find the solution fast. Sudoku is a good example. If one is given a solution to a Sudoku it doesn’t take long to check that it's a valid solution. However, even if it’s possible to verify the solution fast, that doesn't automatically imply that a solution can be found fast and that's the conjecture mathematicians currently have with NP problems.

Göös was recently awarded a prestigious ERC Starting Grant for his proposal “Impossibility Results in Computational Complexity” to tackle this big, open question, but where to begin in the face of such complexity? “I'm trying to rule out at least some types of algorithms for these NP hard problems like Sudoku. We can't show mathematically that there's no efficient algorithm, but at least we can rule out that certain approaches don't give you fast algorithms.”

The open problems that Göös is working on are very ambitious and whilst he reiterates that it’s unlikely that the big question of P versus NP will be solved within his lifetime, his motivation comes from understanding his object of study as well as possible.

“I feel like if you can understand the limitation of something you really, thoroughly understand the thing you're studying. In computation, for example, to come up with an algorithm you just need to have one idea for one way of solving a problem, but it demonstrates a much deeper understanding of something if you can rule out every way of solving a problem, that there's no solution. Working on this problem is exciting because the grand challenge is so difficult that there's an inexhaustible supply of simpler milestones to achieve before the full solution,” he says.

Philosophically, Göös also fundamentally finds the idea of showing impossibility intriguing. He thinks of everyday life and how many times a day that people say something is impossible – things like running a distance in a certain amount of time, jumping a specific height or carrying a designated weight. It only takes the next person to come along and prove you wrong, he says, and we often deem things impossible without enough evidence. He believes that when we say something is impossible we are really just saying that we can’t see how to do it.

“It's only with mathematics that you can unconditionally prove that something is impossible, once it's been proved in mathematics it's true, there's no way around it, and I think it’s only in the realm of mathematics where you can have such provable impossibility.”

Beyond P versus NP and proving impossibility, Göös just tries to be ‘tremendously curious’ about anything that comes his way, “As theoreticians we have the least clue what we're doing. It's easy enough to list all these ambitious problems and say we would like to solve them eventually, but since there's no recipe to approach them, I immerse myself in the world surrounding a problem and maybe I don't solve it but from the journey I learn something unexpected.”

The ERC Starting Grant for the research “Impossibility Results in Computational Complexity” is 1.5 million EUR for a period of 5 years.