Computational Complexity: An Empirical View

International audienceComputational complexity theory (CCT) is usually construed as the mathematical study of the complexity of computational problems. In recent years, research work on unconventional computational models has called into question the purely mathematical nature of CCT, and has revealed potential relations between its subject matter and empirical sciences. In particular, recent debates surrounding quantum computing have raised the possibility of a new computational model, one based on quantum mechanics, which may be exponentially more efficient than any previously known machine. In this paper, I will show how those recent debates suggest an alternative , empirical view of CCT. I will then examine what are the fundamental arguments in the favor of this view, what are its consequences for our conception of CCT as a scientific field, and how further philosophical investigation should proceed