A new perspective on complexity
How much is four times the arctangent of 1? Don't panic, you'll quickly get a numerical approximation of the answer - in this case, pi- if you've got a calculator handy (or very good trigonometry skills). But, in the end, is this calculation easy or difficult? It's not that simple! Classifying and comparing problems according to their difficulty level is a field of computer science in its own right, with both practical and fundamental implications: complexity theory. Manon Blanc, a doctoral student at the Computer Science Laboratory of the École polytechnique (LIX*), is studying these classes of complexity, and along with her thesis co-director Olivier Bournez, has just been awarded the prize for best paper at the international symposium on Mathematical Foundations of Computer Science.
An alternative to Turing's formalism
A complexity class groups together all problems that require a similar amount of resources (such as computation time or memory) to be solved. So, if the time required for a computation grows exponentially with the number of input data for that computation, then that problem will be of exponential complexity in time (EXPTIME class), and therefore very difficult to solve. In practice, "easy" problems that can be solved in a reasonable amount of time are conventionally considered to have a complexity that grows like a polynomial with the number of input data (class P for polynomial).
This convention is designed to ensure that complexity depends solely on the problem itself and not, for example, on the power of the computer used for calculation. These complexity classes therefore need to be precisely defined. To do this, scientists generally use the Turing machine formalism, developed by Alan Turing, one of the leading computer scientists of the 20th century. Turing machines allow each problem to be broken down into elementary operations on binary numbers, according to certain rules. Computation time is defined by counting the number of steps required to solve the problem. "But there are other points of view from which to study complexity classes, and that's the aim of my thesis", explains Manon Blanc.
In their article, Manon Blanc and Olivier Bournez propose a characterization to determine whether a function taking real numbers as input can be computed in polynomial time (and, also, whether the memory required for computation grows polynomially). For example, the arctangent function, like most usual functions, is well within class P. If we wanted to show this with Turing machines, we'd first have to explain how to calculate this function, describe a program capable of approximating it, decompose it into steps with the appropriate formalism... With this new result, it's enough to show that the function belongs to a simple group of functions whose properties are presented in the article by the two researchers.
A fundamental and pedagogical interest
This new way of looking at complexity classes stems from an original question in this field: what can we calculate with computers, which don't work in binary, but on analog quantities? "Our computers work with binary logic: 0 or 1. But they are made of electronic components, whose physics is not described in binary terms, but by differential equations. There's nothing to stop us building analog computers," explains Olivier Bournez, who keeps a few analog computers in his office and has been researching these issues for several years. It is by taking up these ideas, and in particular the tool of differential equations, that they have obtained this result. In addition to its fundamental interest, the authors see it as a pedagogical tool, enabling them to talk about complexity to students who are often more familiar with the concept of functions, taught in high school, than with that of Turing machines. Manon Blanc, who intends to continue studying complexity from different points of view, finds an added interest: "Above all, it's pretty math, and pretty theoretical computer science, which is fun!"