Maël Pégny

Computational Complexity: An Empirical View

Computational 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.

Introduction: unconventional computing and philosophy

In the last decades, computer scientists have been showing a growing interest in the study of unconventional computational models. Those models stem from a broadened understanding of computation. In his original paper, A. Turing made it clear that his model was explicitly inspired by human, pen-and-paper computation (see [START_REF] Turing | On Computable Numbers, with an Application to the Entscheidungsproblem[END_REF], section 9). In many unconventional computational models, computation is no longer reduced to the discrete process of pen-and-paper computation: computation is any process that allows the encoding of an input value into the state of a given system, the processing of that information according to a given specification, and the reading of an output value. Physical, chemical and biological processes can be harnessed to perform computations in this broadened sense. Algorithms can no longer be conceived as abstract mathematical methods whose conception and theoretical properties are completely independent of implementation: algorithms now become abstract models of empirical processes. This new approach to computing raises new challenges for computer scientists. In the case of Turing machines, and other historical models, empirical realizability was not a pending issue. The possibility of implementing these models by pen-and-paper computation was built into their very design. Many unconventional computational models, on the contrary, raise more serious issues of empirical realizability. Furthermore, defining the set of computable functions, or computational costs, according to these models, might depend on considerations of empirical realizability. In this broadened framework of computation, it becomes natural to think that not only logical and mathematical arguments, but also empirical ones, are relevant to decide whether a given model is realistic, and what its exact computational power is.

To the extent of my knowledge, there is a striking assymetry in the philosophical litterature 2 between the treatment of computability issues and that of complexity issues, when it comes to analyzing the role of empirical considerations. Foundational issues of computability, especially the debate on the possibility of hypercomputation, have been the object of intensive scrutiny (see [START_REF] Gandy | Church's thesis and Principles for Mechanisms[END_REF], [START_REF] Arrighi | The physical Church-Turing thesis and the principles of quantum theory[END_REF], [START_REF] Sieg | Church without dogma: Axioms for computability[END_REF], [START_REF] Piccinini | The Physical Church-Turing Thesis: Modest or Bold?[END_REF], [START_REF] Davis | The Myth of Hypercomputation[END_REF], to mention only a few references). The relations between computational complexity and empirical considerations have been the object of a somewhat lesser attention (see [START_REF] Pitowsky | The physical Church thesis and physical computational complexity[END_REF], [START_REF] Pitowsky | Quantum Speed-Up of Computations[END_REF], [START_REF] Hagar | Quantum Algorithms: Philosophical Lessons[END_REF], [START_REF] Hagar | The Complexity of Noise: A Philosophical Outlook on Quantum Error Correction[END_REF], [START_REF] Vergis | The complexity of analog computation[END_REF], [START_REF] Aaronson | NP-complete Problems and Physical Reality[END_REF], for a few remarkable exceptions). In particular, how this empirical turn might affect our conception of CCT as a discipline has not been the subject of a systematic philosophical treatment. The aim of this work is to synthetise the dispersed remarks present in the literature, and to provide such a systematic treatment.

After articulating the orthodox, mathematical conception of CCT (section 1), I use recent analysis of the Extended Church-Turing Thesis (ECTT) to present an empirical interpretation of CCT (section 2). I then examine how research on unconventional computational models, especially quantum computing, can support arguments in favor of this empirical interpretation (section 3). Finally, I discuss how this interpretation offers a new vision of the subject-matter of CCT, and its unity as a scientific field: CCT can be seen as an empirical science, founded on empirical hypotheses (section 4)

The subject-matter of CCT, and the nature of computation

What is the object of computational complexity theory (abbreviated as CCT3 )? In the literature, CCT is usually defined as a mathematical science quantifying and studying the difficulty of mathematical, computational problems ( [START_REF] Goldreich | Computational Complexity[END_REF], [START_REF] Arora | Computational Complexity. A Modern Approach[END_REF]). Two remarks must be made to properly understand this definition. First, complexity properties are, prima facie, properties of algorithms. They become intrinsic properties of a given problem through optimality results, which demonstrate that no algorithm can do better than a given, optimal one. It is this quantification over all possible algorithms, and the quest for optimality results, that distinguishes CCT from Algorithmic Analysis.

Second, and foremost, CCT as a domain rests on three distinct hypotheses concerning the nature of its subject matter and the nature of its results:

• Hardware-independence. CCT concepts and results are independent of low-level hardware details. This is one of the central reasons why the number of steps needed by a given algorithm is described up to a linear factor, using the O notation. The exact number of steps taken by an algorithm on a given machine could be sensitive to hardware details, but its gross magnitude should not show that sensitivity. • Model-independence. To be well defined, computational costs must be considered within a given computational model, i.e. a mathematical model describing precisely how algorithmic instructions are to be written, and how they are to be executed. But the main concepts and results of CCT are independent from any particular choice of model, e.g. Turing machine, or register machine. The first two hypotheses explain why CCT can be seen as a mathematical, abstract theory of computational problems. The third one states that its concepts and results remain relevant for concrete machine implementations. This is the reason why CCT can also sometimes be defined as a branch of engineering, one that quantifies and studies the resources needed by a computer to solve a given problem, without creating any philosophical controversy [START_REF] Papadimitriou | Computational Complexity[END_REF].

From these three hypotheses, a vision of computation, and its complexity, can be reconstructed. Computation is an abstract process that can be studied a priori by a mathematical theory. The results of this theory determine constraints relevant for any device that implements that abstract process: real runtime and memory size are thus determined to a certain order of magnitude by the logical steps described by the instructions of the algorithms.

This rather natural view of computation, and its complexity, has been called into question by recent work in unconventional computational models. Since this criticism mainly stems from recent challenges made to the hypothesis of model-independence, I will first take a closer look at it. [START_REF] Abrams | Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems[END_REF] The core issue: model-independence and the Extended Church-Turing Thesis

The rigorous expression of model-independence is a specific hypothesis lying at the foundations of CCT, called the Extended Church-Turing Thesis (henceforth abbreviated as ECTT):

All reasonable computational models are simulable by a Turing machine with at most polynomial overhead.

All the proven relations of efficient simulation between models that have been explored so far provide evidence for this thesis. But as the list of computational models is open-ended, it currently remains a working hypothesis. It is not a mathematical proposition, and thus can be neither demonstrated nor taken as an axiom.

Despite its informal character, the ECTT is a fundamental hypothesis of CCT for at least two reasons. First, the ECTT allows complexity theoretists to reason within one particular model, most frequently Turing machines, knowing that any result regarding the polynomial or superpolynomial time-complexity of a given problem will remain untouched by a change of model. Without the ECTT, complexity properties could not be attributed to computational tasks in an absolute sense, but only relatively to a given model. The second reason is that the model-independence of polynomial time is one of the main arguments for the identification of polynomial-time complexity with tractability, and superpolynomial time-complexity with untractability (see, for instance, [START_REF] Nielsen | Quantum Computation and Quantum Information, Cambridge series on information and the natural sciences[END_REF]).

The obvious escape in ECTT is the adjective "reasonable." It suggests the existence of computational models that go beyond the limits drawn by the ECTT, but are characterized as 'unreasonable.' Yet without any specification of what a reasonable computational model should look like, the ECTT is not only informal, but also not welldefined.

In recent years, several computer scientists and physicist, including P. Shor, U. Vazirani, E. Bernstein and D. Aharonov suggested that "empirically realizable"4 should be substituted for "reasonable" in the above phrasing (see [START_REF] Shor | Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[END_REF], [START_REF] Bernstein | Quantum complexity theory[END_REF], [START_REF] Aharonov | Is Quantum Mechanics Falsifiable? A computational perspective on the foundations of Quantum Mechanics[END_REF]). The suggestion is quite natural, since empirical realizability is a necessary condition of implementation.

A straightforward identification of "reasonable" with "empirically realizable" might nevertheless be questionable. As P. van Emde Boas noticed in [START_REF] Van | Machines Models and Simulation[END_REF], a computational model might violate the ECTT simply because of a bad choice of data representation. There is no relation of efficient simulation between an unary Turing machine and a Turing machine with a shorter data representation but it is yet empirically realizable. A reasonable computational model might be defined only up to a convenient choice of data representation. Other similar conditions, independent of empirical realizability, might be added to an improved understanding of what a reasonable model is. For the sake of caution, one might distinguish a special, empirical ECCT (All empirically realizable computational models are simulable by a Turing machine with at most polynomial overhead) from the original, general ECCT. The empirical ECCT is not an autonomous proposition but a simple subhypothesis of the general ECCT: if it turns out to be false, the general ECCT would be refuted. Even if the ECTT is not reduced to an empirical hypothesis, it would still depend on such an empirical hypothesis 5 . This being said, we can drop the distinction between the empirical ECTT and the general ECTT for the sake of conciseness.

We may then consider an empirical interpretation, or empirical view, of computational complexity, based on the following statement: a valid definition of a reasonable computational model, and a valid definition and evaluation of computational costs within a computational model, should take into account the empirical factors of empirical realizability. The value of this proposition is essentially heuristic, since we do not have a definition of what a reasonable computational model is. It simply warns computer scientists, that they should take empirical factors into account, when they discuss the reasonableness of a given computational model.

This proposal opens a new vista on the subject-matter of CCT, since it lays at its foundations an empirical hypothesis, which might be refuted by further empirical findings. The purely a priori nature of CCT as a discipline might thus be called into question. A proper account of computational complexity should take into consideration the empirical conditions of implementation. As P. Shor explicitly remarked, the success of our mathematical models of computation might have blinded us to this seemingly elementary fact, tricking us into thinking that computational complexity was a purely abstract, a priori topic.

With this interpretation in mind, it is easy to see the reason why the ECTT should not be considered an implicit definition, as P. van Emde Boas proposed [START_REF] Van | Machines Models and Simulation[END_REF]. If one thinks that the ECTT should be a mathematically well-defined proposition, then one can only be disturbed by the lack of definiteness of the notion of "reasonable model". At first sight, it would seem relevant to consider that statement as a implicit definition of the notion. But one would then be unable to use this concept to discuss the merits of original computational models, which is a quite unpleasant consequence.

An empirical view can help us out of this dead-end. The basic concepts of physics, for instance, are never defined with perfect mathematical rigor. Think for instance of the wave-packet reduction principle in quantum mechanics: when a measurement occurs, the wave function of the measured system collapses to an eigenstate of the measured observable. It does not tell us precisely what counts and what does not count as a measurement, and this has precisely been a topic of discussion in the interpretation of quantum mechanics. But it would nevertheless be foolish to think that it is an implicit definition of what a measurement is, and it does not keep physicists from believing that they would acknowledge a counter-example to that principle if they met one. In mathematics, you cannot speak of a counter-example to a proposition that is not rigorously defined. That is not the case in empirical sciences: physicists agree that they would acknowledge a counter-example to basic physical principles, even if a basic principle is never defined with perfect rigor, and there is always room for interpretation. In that sense, physical principles, if they cannot be demonstrated, can be falsified, and have to be construed as genuine propositions, not mere definitions.

In a similar fashion, we might not be able, and we should probably not try to reach mathematical rigor in the definition of what a reasonable computational model is. It should not keep us from discussing the issue, and it will not keep us from acknowledging a counter-example to the ECTT if we ever meet one. Thus, the empirical interpretation of the ECTT illuminates its present status, and the understanding that we should have of it. It is a empirical proposition, that cannot be demonstrated, but can both be falsified by a relevant counter-examples, and corroborated inductively by the rebutting of alleged counter-examples, just as our fundamental physical principles are corroborated by years of resistance to seemingly adversary experiments.

How empirical considerations are brought into CCT: unconventional computational models

Let us now see how one can argue in favor of this empirical interpretation. Before we come to the main argument, namely the current debate around quantum computing, let us put the problem into a larger perspective, by presenting quantum computing as one among many other unconventional computational models.

A fundamental distinction has to be drawn between two different questions: the relevance of empirical considerations in the definition of a computational model, and the success to implement this or that unconventional model. Many unconventional models are blatantly unreasonable, but the very reasons why they are deemed so make them relevant for the discussion of the empirical view of computation. If the arguments formulated to dismiss exceptional complexitytheoretic performances are empirical, then the empirical interpretation of complexity is supported by the following counterfactual argument: if empirical facts of the matter have been different from what they actually are, then it would have been possible to achieve exceptional computational performances, such as the violation of the ECTT. The truth-value of the empirical interpretation of complexity does not depend on the success or failure to implement some unconventional computational model, but on the specific reasons for this success or failure.

Depending on the computational model under scrutiny, the "empirical facts of the matter" mentioned in the antecedent can vary greatly in nature. In certain cases, such as quantum computing with non-linear variants of Schrödinger's equation [START_REF] Abrams | Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems[END_REF], the computational model contradicts well-established principles of some physical theories. In other cases, such as computing with Closed Timelike Curves, a controversial aspect of some accepted theory, i.e. General Relativity, is put to use (see [START_REF] Earman | Forever is a day: Supertasks in Pitowsky and Malament-Hogarth spacetimes[END_REF], for a critical appraisal). In still other cases, the computational model makes use of a formal possibility that would be deemed unrealistic by most physicists, such as arbitrarily precise control or measurement of a given system, even though for the time being no fully established principle explicitly forbids such a possibility (see [START_REF] Aaronson | NP-complete Problems and Physical Reality[END_REF] for a comprehensive review).

Among all unconventional computational models, quantum computing (abbreviated as QC) has drawn an exceptional amount of attention from the CCT and physics community. To this day, QC is the only computational model violating the ECTT that has been the object of intensive scientific scrutiny, with entire research groups working on both theoretical and experimental aspects of the problem.

What makes QC so special? In 1994, P. Shor published an efficient algorithm to factorize integers using a quantum computational model [START_REF] Shor | Algorithms for Quantum Computation: Discrete Logarithms and Factoring[END_REF] 6 . This result was striking mainly for two reasons. First, factorizing integers was, and still is believed to be hard on a Turing machine: it is thus likely that Shor's algorithm violates the ECTT. Second, quantum computing is not based on a blatantly unrealistic model, but on our best-confirmed physical theory, and it is not obvious to say that it misconstrues this theory.

For very small input sizes, prototypical quantum computers have already been implemented and shown to work. Nevertheless, a true demonstration of the extra computational power of quantum computers would require the use of large inputs to study how computational time scales with input size. This has not yet been achieved and would represent a considerable experimental challenge. Thus the possibility of a large-scale quantum computer is still a controversial topic.

From our philosophical perspective, one argument used by QC enthusiasts has special interest. The relevance of research in quantum computing has been defended on the basis of an "either way I win" argument. Trying to build a large scale quantum computer would be a topic of major scientific interest, because if we were successful, we would have shown that the ECTT could be violated, and if we were not, since quantum computing is compatible with quantum theory as we know it, we would have proven quantum theory wrong. The debates on the possibility of quantum computing exhibit the dependence of a complexity-theoretic question -does there exist a reasonable computational model violating the ECTT? -to non-trivial, open questions in quantum theory, such as the possibility to protect large quantum systems against decoherence, the exact precision to which a quantum system can be controlled, the exact accuracy to which quantum-theoretic predictions hold (see, for instance, [START_REF] Nielsen | Quantum Computation and Quantum Information, Cambridge series on information and the natural sciences[END_REF] and [START_REF] Aaronson | Multinear Formulas and Skepticism of Quantum Computing[END_REF]). Even if a large-scale quantum computer turned out to be impossible, one could still formulate a particularly strong counterfactual argument in favor of the empirical interpretation: if any, or several of the aforementioned facts had been different from what they actually are, then we would have violated the ECTT. The particular strength of this argument would come from the necessity to refute the possibility of efficient quantum computing of gathering new information about the physical world, as opposed to just using already well-established physical principles, or exerting skepticism towards already criticized models.

The "either way I win" argument has of course been criticized (see for instance [START_REF] Levin | The Tale of One-Way Functions[END_REF], section 2). In this paper, I do not intend to discuss this argument with all desirable precision and I will just make the following, heuristic remark. The "either way I win" argument is the proper place to discuss the empirical interpretation of complexity because it states that even if quantum computing fails to violate the ECTT, it will fail for interesting, empirical reasons.

Philosophical implications

CCT as a mathematical theory of computational problems: a critical appraisal

In the current state of affairs, there are significant, if not compelling, arguments in favor of the empirical interpretation of complexity.

Leaving to further investigation the strengthening or correction of these arguments, the philosopher can wonder how this empirical terpretation, if it turned out to be vindicated, would change some of our fundamental intuitions about the subject matter of CCT, and the very nature of computation.

If one admits the validity of counterfactual arguments, the empirical interpretation of complexity can be considered as independent from the truth of the ECTT. Even if the ECTT is vindicated from all the different trials to which it has been subjected by unconventional computational models, it will have been established that CCT rests on a fundamental empirical postulate, and is therefore an empirical science.

This last remark calls into question our initial vision of CCT as a mathematical study of complexity properties of problems. If the empirical interpretation is vindicated, it would no longer be possible to demonstrate that a given problem, construed as an abstract mathematical entity, has certain computational complexity properties. As we have seen above, the ECTT, along with the existence of optimal algorithms, is necessary to attribute complexity properties to problems, and not just to algorithms. If the ECTT depends on a true empirical postulate, namely the empirical ECTT, then the attribution of complexity properties to a problem is not a mathematically provable result, demonstrated with purely a priori means, but an empirical result, which might be refuted by new empirical findings.

However, if the ECTT is false, then it is no longer possible to consider that the polynomial-superpolynomial time-complexity of a given problem as an intrinsic property of that problem. This is particularly obvious in the case of quantum computing. If a large-scale quantum computer is empirically realizable, then the same problem, FACTORING, will be polynomial on a quantum computer, and superpolynomial on a classical computer. Of course, it would still be possible to talk about the "complexity of the problem," to designate the complexity of the most efficient known algorithm solving that problem. But that property would be an extrinsic property of the problem, depending on the machine model at hand.

Complexity properties could still be attributed to algorithms, but a new vision of their relation to implementation would emerge, especially if a large-scale quantum computer is feasible. Again, this is particularly obvious in the case of quantum computation. Shor's algorithm can be simulated by a Turing machine, and thus by a classical computer. But this simulation would not preserve its complexity properties and create exponential slowdown. It is only on a true quantum computer that the desired complexity properties of this algorithm could be achieved. If complexity properties were still conceived as intrinsic properties of algorithms, this last remark would call for a reassessment of the distinction between hardware and software. An algorithm like Shor's algorithm is not "portable", in the sense that its complexity-theoretic advantages would be destroyed by classical implementations. But it is not so much dependent on the technological details of hardware than on the underlying physics of the hardware, as I will now demonstrate.

The unity of CCT as an empirical science

If CCT subject matter can no longer be conceived as complexity properties of problems, how can we conceive of it? As we have seen above, the ECTT guarantees that fundamental distinctions of CCT are robust. As we have previously seen, it also guarantees the pacific coexistence of two presentations of CCT: a pure mathematical discipline, and a study of the actual performances of real-world computers. If the ECTT is false, one would then be tempted to consider CCT as some branch of engineering, studying the properties of multifarious computational models, without any systematic unity. But this conclusion, I will argue, is not warranted by our previous analysis. To better understand how CCT maintains its unity as a scientific discipline, one has to take a closer look at the fundamental hypotheses of CCT.

First, I call "physics-dependence" the hypothesis that complexitytheoretic properties of a given computational model depend on underlying physical assumptions of this model. Physics-dependence should be distinguished from hardware-dependence. This distinction is more easily explained by considering quantum computers. A quantum algorithm depends on quantum properties of the system used for implementation, but it does not depend on the particular technological detail of that implementation. From a complexity-theoretic point of view, it does not really matter whether a quantum computer is made out of trapped ions or photons, to mention two actual implementation strategies. CCT is still independent from hardware details, even if it is no longer independent from the physics underlying that hardware.

Secondly, physics-dependence should also be distinguished from model-dependence. These last two decades have seen the birth of many different quantum computational models: quantum Turing machines, quantum circuits, quantum cellular automata, one-way quantum computer, topological quantum computation, quantum adiabatic computation, and several high-level models such as quantum lambda-calculi, quantum flow-charts, and categorical quantum languages. This list is of course open-ended, just as the list of "classical" computational models is open-ended. The study of the relations of efficient simulation between all these models raises exactly the same issues as before. Many of these models have been demonstrated to be polynomially equivalent (see, for instance, [START_REF] Chi | Quantum Circuit Complexity[END_REF], [START_REF] Raussendorf | Measurement-based quantum computation on cluster states[END_REF]), but the question has been raised whether a given model, namely quantum adiabatic computation, could be more powerful than other quantum models, allowing the computation of NP-complete problems in polynomial time [START_REF] Fahri | A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem[END_REF]. This idea has been criticized along customary lines for not being empirically realizable [START_REF] Aaronson | NP-complete Problems and Physical Reality[END_REF].

Even if the hypothesis of model-independence in all generality is false, it becomes possible to formulate a milder form of the ECTT: all realistic computational quantum models are intersimulable with at most polynomial overhead. This new form is relativized to an underlying set of physical assumptions. What unconventional computational models suggest is not so much a dependence of complexity-theoretic properties on a particular model, but a dependence on the physical hypotheses underlying a class of models. Thus it is preferable to present the subject-matter of CCT as the study of the resources needed to solve some computational problem on a given class of computers, characterized by a common set of physical assumptions. If CCT had to be compared with any other branch of knowledge, it would be wiser to compare it with mathematical physics, studying the various computational potentials of different physical theories, than it would be to classify it as a branch of engineering. But it is not necessary to assimilate CCT to any existing discipline, and we can consider it as an empirical discipline on its own. This view, however, remains problematic. For about two decades, physicists and computer scientists have tried to pinpoint what exact feature of quantum theory would cause the supposed exponential speed-up a quantum computer might provide and the question remains controversial (see, for instance, [START_REF] Bub | Quantum computation: Where does the speed-up come from[END_REF]). Consequently, it is hard to explain what "classical" means in "classical computational model." Worse still, models inspired by pen-and-paper computation, such as the Turing machine, do not make any explicit reference to classical physics. The input is not encoded in the state of a classical system, the dynamics of the system is not made explicit, and no mention is made of measurement. The model is classical only in the loose sense that it is not quantum: it does not make any use of specific quantum properties such as state superposition and entanglement. Even if one subscribes to the idea that CCT is physics-dependent, fleshing out this idea is a difficult task.

Nevertheless, if this view were vindicated, it would explain why CCT could maintain a systematic unity as a field, instead of just being a conjunction of computational models without any theoretical relation to one another. The different sets of physical assumptions made by different classes of computational models need not have an empty intersection. Even if the ECTT is false, some weaker physical hypothesis might still hold, and could be substituted to the ECTT at the foundations of CCT. This physical hypothesis would be respected by every class of computational model and thus unify CCT as a field.

To better explain this point, it is necessary to understand which part of CCT could be shattered by new computational models and which part could remain untouched. If a large-scale quantum computer is empirically realizable, the time-complexity of a given problem depends on the selected computational model. This would not imply that the distinction between polynomial and superpolynomial complexity classes should be abandoned, or even the distinction between P and NP for that matter. In the current state of art, FACTOR-ING is conjectured to be in NPI, the classes of problems in NP that are neither in P nor NP-complete: the existence of an efficient solution to that problem does not imply that P = NP. Some of the models we have presented above make bigger promises, pretending to solve NP-complete problems in polynomial time, or even to solve efficiently all problems in a class larger than NP. As we have seen, these models are considered far less likely to succeed than the quantum computer, but the failure of an attempt is not the failure of an idea. Should we expect further developments in physics and unconventional computational models to yield such extraordinary results (see [START_REF] Pitowsky | The physical Church thesis and physical computational complexity[END_REF] for an interesting discussion of this point)? In recent years, quantum complexity theorist S. Aaronson has defended the exact opposite view [START_REF] Aaronson | NP-complete Problems and Physical Reality[END_REF]. Not only we should not expect such a complexity-theoretic wonder, but we could even state its impossibility as a physical principle, the "No SuperSearch Principle" (aka "NP-hardness Assumption"): there is no physical means to solve NP-complete problems in polynomial time.

S. Aaronson's main argument for this principle is the following: if an efficient solution of an NP-complete problem were possible, it would trivialize many problems we strongly conjecture to be hard. For any usual axiomatic system A, the following problem is in NP: T HEOREM S = {(φ, 1 n ) : φ has a f ormal proof of length ≤ n in system A}. Even if no algorithm can decide every mathematical conjecture, there is a simple search algorithm that decides whether there exists a proof of length inferior to a given bound. If there were, thanks to some unconventional computational model, an efficient algorithm for this problem, it would become possible to "solve practically" any mathematical conjecture, by examining only proofs of reasonable length, e.g. a length inferior to the number of particles in the Universe. We would then have access to a form of automated mathematical research, despite the negative solution to the Enstcheidungsproblem. The P-NP problem can thus be seen as a bounded ressources version of the Entscheidungsproblem. Such implausible computational wonder should be explicitly excluded by a new physical principle, the No SuperSearch Principle, which would perform the function of the unifying hypothesis we mentioned above.

The previous argument might be questionable. It only justifies the proposed principle in terms of apocalyptic consequences for our understanding of mathematics and does not provide a proper physical ground for its acceptance. It has nevertheless a great heuristic value, for it demonstrates how much is at stake in the interpretation of CCT.

Without further developing S. Aaronson's arguments for that new principle, I would like to comment on the insight this proposition gives us on the new relations between physics and CCT allowed by the empirical interpretation of complexity. Once we accept this interpretation, it opens a two-way street between theoretical physics and complexity theory. We should not only expect that new insights from physics might shatter complexity-theoretic conjectures, established results and concepts, but we should also expect new insights on physics coming from CCT. Some CCT concepts, like the distinction between polynomial and superpolynomial complexity classes, might have a deep and physically robust meaning. Computation should not only be considered as a tool used by physics, but also as a subject matter of physics, whose properties are to be defined and studied from a physical point of view (for a similar position, see [START_REF] Hagar | Quantum Hypercomputation-Hype or Computation?[END_REF]).

Conclusion

The aim of this brief work was less to defend a thesis than to raise an issue. A comprehensive discussion of the arguments pro and contra the empirical interpretation would demand another article. I will be content if I have convinced the reader that the empirical interpretation of CCT is a legitimate problem.

I have also given indications on how further discussion of this interpretation should proceed. From this perspective, I tried to show that there is much at stake in the current scientific debate on the feasibility of quantum computing. The problem is not only relevant for physicists, computer scientists, and amateurs of high-end technol-ogy, but for philosophers as well. Philosophers do not even need to wait for the definite resolution of this scientific controversy to show interest. If the "either way I win" argument is correct, complexity theory is physics-dependent, even if a large-scale quantum computer finally turns out to be unfeasible. This argument, which might be a topic of interest for philosophers studying counterfactual propositions, should be placed at the core of further discussion of the empirical view.

This view, if it were vindicated, would call for a radical reappraisal of the epistemological status of computational properties, which I have only been able to sketch out. These properties would no longer be the object of pure a priori knowledge, but should be seen as theoretical properties of the empirical processes that are harnessed to perform computation. This should be of interest not only for the philosophy of physics or computer science, but also for the general philosophy of knowledge, especially the debates concerning a priori knowledge.

  • Relevance for implementation. Despite hardware and model independence, CCT results are relevant to determine the concrete values of time-interval, and memory size, needed by a concrete device when it executes a given algorithm.

Université deParis-1, CEA-Larsim, France, email: Mael.Pegny@malix.univ-paris1.fr

By "philosophical literature", I do not only mean the literature written by professional philosophers, but also the foundational considerations published by physicists, computer scientists, and logicians.

[START_REF] Abrams | Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems[END_REF] I will actually focus my attention on uniform computational complexity theory. The reason for this restriction is simply that I am only interested in computational models that can actually be implemented. If one thinks of the characterization of non-uniform complexity classes by resource-bounded Turing Machines receiving advice, one immediately faces the problem of the actual origin of such an advice. In full generality, it is unclear whether non-uniform computational models can be considered as empirically realizable models, or if they are to be considered as abstract tools used by the theorist. Even though that might be a very interesting philosophical issue, I do not think that such a short, synthetic work is the proper place to discuss such details.

The most commonly used phrase is "physically realizable". But I prefer to avoid the common philosophical ambiguity associated with the adjective "physical," which refers both to any empirical entity or process, and to the entities or process that are explicitly modelized by physics. P. Shor clearly had the second acception in mind, since he writes[START_REF] Shor | Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[END_REF] : Researchers have produced machine models that violate the above quantitative Church's thesis, but most of these have been ruled out by some reason for why they are not "physical;" that is, why they could not be built and made to work.

Our inability to demonstrate the ECTT should not be attributed to a mere lack of definition, but to this very dependence on an empirical hypothesis, which cannot be proven.

There exist other results indicating that a quantum computer might be more powerful than any conventional, "classical" model (see, for instance,[START_REF] Lov | Quantum Mechanics Helps in Searching for a Needle in a Haystack[END_REF]). But Shor's algorithm is the only known example that provides an exponential speed-up over conventional models.

ACKNOWLEDGEMENTS

I would like to thank my Phd advisors, A. Grinbaum and J.B. Joinet, and the anonymous reviewers, for their comments of earlier drafts. I would also like to warmly thank Evan Spritzer, for the time he benevolently took to improve the redaction.


Riccardo Artoni
email: riccardo.artoni@ifsttar.fr

Andrea Santomaso
email: andrea.santomaso@unipd.it

Effective wall slip in chutes and channels: experiments and discrete element simulations

Keywords: 47.57.Gc, 45.70.-n, 83.80.Fg dense granular flows, wall slip, scaling laws, experiments, discrete numerical simulations

Wall slip is an important phenomenon for the flow of granular materials in chutes and channels. The appearance of a slip velocity at the wall critically affects wall stresses and flow profiles, and particularly the total flowrate. In this work we show, through numerical simulations and experiments, that the global slip phenomenon at a wall has peculiar features which deviate significantly from simple sliding behavior. At first we present experimental data for the vertical chute flow which highlight that wall slip depends on many operating and system variables such as flow rate, material properties, wall properties. Secondly, we resume a large campaign of numerical data performed in 2D with polygonal particles, and try to analyse the effect of material properties, contact parameters, operating variables, different flow configurations, on the slip phenomenon. The numerical campaign allowed to identify the main parameters affecting the wall slip behavior of a numerical model of granular flow, providing the ingredients for the creation of a framework for the description of wall slip.

Introduction

The slip behavior of a granular material densely flowing on a flat frictional boundary is still poorly understood, despite the extensive work done with respect to bulk rheology of dense flows [1] and boundary conditions in other flow regimes [2]. The development of scaling laws for the slip velocity is not only an important theoretical issue which was barely addressed in the past, but also a practical challenge critically affecting the predictions of rheological models. Few works have up to now addressed the problem of interface rheology and wall slip in dense granular systems [3][4][5][6][7][8].

In this work we present recent experimental and numerical results on wall slip behavior of granular materials, trying to trace a route for the development of such scaling laws. At first, experimental results of vertical chute flow are discussed, for different bulk and wall materials. General features of slip behavior are then analysed, with a particular focus on the joint effect of internal friction, wall roughness and flow rate. In order to understand the underlying contact scale mechanisms, extensive numerical simulations were carried out; in particular, the simulations allowed to study the effect of the internal variables (shear rate, stresses, particle size, ...) on the slip velocity at a wall. Simulations were carried out in 2D for different flow configurations and particle shapes. Relevant dimensionless numbers were identified, and therefore a functional form for the scaling law was proposed, the generality of which was analysed and discussed.

Vertical chute experiments

Materials and method

The experimental set-up consisted of a quasi-2D vertical chute, i.e. a rectangular channel (a sketch of which is provided Figure 1a) where one horizontal dimension (which we will call thickness) was much less than the other (the width). The downward motion of the material was controlled by means of a moving plate. An electric motor equipped with a linear reducer was used to control the velocity of the plate. The plate velocity range spanned nearly over two orders of magnitude, from 0.045 to 2.2 cm/s, in order to test the material behavior in a wide range of flowrates. The channel had a variable width (10-20-30 cm) and a variable thickness (15-30-45 mm). Data presented here are for the smallest thickness and width; it was verified that the width had no effect on velocity profiles, and thickness was kept small in order to avoid the development of velocity profiles in the transversal direction. Lateral walls (i.e. walls corresponding to the thickness) were roughened with 40 grit and 120 grit sandpaper (corresponding to a grit particle size of 425 µm and 125 µm respectively). The other two walls were made of glass in order to reduce friction and allow visualization of the flow. A campaign was made with particles of different materials and size, which properties are listed in Table 1. The values of the angle of internal friction φ and of the angle of wall friction φ w were determined using a laboratory shear cell tester, the Brookfield Powder Flow Tester (PFT).

A CCD camera (mvBlueFox) was used for the image acquisition. The camera recorded a zone near a wall, and was driven downward at the same velocity of the moving plate (as depicted in Figure 1a). The frame rate was varied as a function of the plate velocity (from 10 to 25 fps). At least 300 frames (512x512 pixels) were acquired for each run, representing a square of side ≈ 3 cm. Images were acquired with the vendor software and then processed (cropped, resized, subsequently analyzed) in Matlab. Velocity profiles were computed using a cross correlation Particle Image Velocimetry (PIV) technique, with a code derived from the freely available code Matpiv [9]. For each plate velocity (9 values were chosen), the test was repeated three times. The PIV analysis allowed to reconstruct the velocity profile of the granular material in the direction perpendicular to the wall.

Results

According to the literature [10,11], the velocity profile in vertical chute flow corresponds typically to that sketched with its characteristic variables in Figure 1b: shear is localized near the walls, in a shear band which width δ is of 5 to 10 particle diameters, while the rest of the material is in plug flow. In this work we are concerned with the slip behavior at the wall; a discussion on the full velocity profile will be therefore given elsewhere.

For present, we will be content to say that we recovered the typical qualitative velocity profiles referenced above also in our experiments.

In order to characterize wall slip from velocity profiles, it was chosen to use the slip length λ,a quantity which was suggested already by Navier [12], and which is defined by the ratio between the slip velocity v slip and the velocity gradient at the wall, γw = dv/dx| x=W :

λ = v slip γw . (1)
In the following we will refer to a dimensionless slip length λ/d p . From tests performed with the same material and different particle sizes, it was indeed verified that the slip length scaled with particle diameter. This was not surprising, since the particle diameter is the only intrinsic length scale of a granular system. Results from the experiments were sometimes difficult to interpret, because the rescaled slip length appeared to depend generally on many system parameters such as flowrate, internal friction of the material, wall roughness (or wall friction coefficient). An accurate analysis of the results revealed that the materials used for the tests could be divided in two classes determined by the value of the angle of internal friction: class A, characterized by less frictional materials, for φ < 34 • (iron, steel shots, cellulose), and class B, for φ > 34 • , containing more frictional materials (TAED and calcium carbonate); it has to be noted that the value of 34 • for the transition angle is only given as a crude estimate, due to the discrete nature of the data. Class A materials were characterized by a sharp dependence of the slip length on wall roughness. While for the roughest wall the slip length was found to be independent of flowrate, with values less than 2 particle diameters, for the less rougher wall the same materials showed a strong monotonic increasing dependence on flowrate, with λ starting from around 5 particle diameters up to around 25 particle diameters for the higher velocities. On the other hand, class B materials were always characterized by an increase of the slip length with flowrate, but displayed a weaker dependence on wall roughness. Figure 3 synthetically displays these issues. In order to resume the results, in the figure we plotted the average value of the dimensionless slip length, together with the maximum and minimum values. The relative wall roughness d R /d p is used as a roughness parameter, where d R is the typical dimension of wall roughness elements.

3 Numerical Simulations

Simulation method and parameters

The experimental results allowed to appreciate the complex picture associated with wall slip and its main trends. In order to refine the analysis and try to determine scaling laws for the slip velocity, discrete numerical simulations were carried out. Focusing on dense granular flows over flat frictional walls, a large plan of 2D simulations was carried out, varying (1) flow configuration, (2) particle-wall friction, (3) particle shape, (4) particle diameter an (5) flow configuration parameters (flow depth and inclination in inclined chute flow, channel width in vertical chute and simple shear flow). We focused on two dimensional simulations, in order to perform a larger number of runs and identify there the scalings to be then tested in 3D. Discrete element simulations were carried out using the Contact Dynamics method developed by Moreau and Jean [13] and implemented in the open source platform LMGC90 [14]. The study was focused on irregular particles (polygons): as a model of polygonal particle with a strong angularity, pentagons were chosen. The initial sample was slightly polydisperse in all the runs, uniformly distributed in a range d p ±0.1d p . Interparticle and particle-wall interactions were chosen as completely inelastic, with Coulomb friction for long lasting contacts. While the interparticle friction coefficient µ p was kept constant and equal to a typical value adopted in literature (µ p = 0.3, with no connection with the experiments presented above), the particle-wall friction coefficient µ pw was generally varied, as reported, together with the other simulation parameters, in Table 2. A sketch of the different flow configurations simulated is given in Figure 4. For each test, after the system reached a steady state, continuum averages of velocity and stresses were obtained, as discussed in [8]; subsequent analyses were based on these continuum averaged values.

Inclined chute flow

For the inclined chute flow, the results were discussed in more detail in [8]. If a simple sliding Coulomb boundary condition was valid, the slip velocity should follow the following behavior: for tan θ < µ pw (where θ is the inclination of the chute) material should experience no-slip at the wall, for tan θ = µ pw a steady sliding phase and for tan θ > µ pw an accelerated sliding phase. In fact, in the simulation results, the average slip velocity was found to be non null for a wide range of tan θ < µ pw . In particular, when changing the basal friction coefficient, it was observed that the velocity profile remained unchanged in its shape (with the shear rate having the typical (H -y) 3/2 scaling with depth), but was shifted of a certain slip velocity. This had a strong impact on the inclined chute flowrate, which was generally larger than the one predictable using a simple sliding boundary condition. In order to analyse results, the system variables were made dimensionless. The relevant dimensionless variables at the wall were identified as: (1) the inertial number I = γdp √ p/ρp , (2) the particle-wall friction coefficient µ pw , (3) the effective friction coefficient at the wall µ w = τ /σ w where τ is the shear stress and σ w is the normal stress in the direction perpendicular to the wall, and (4) the dimensionless slip length

v slip γdp .
For the inclined chute configurations (with both regular and elongated particles), a scaling law was found relating three of these four parameters, a good fitting of which was found to be

Other flow configurations

In order to test the validity of the scaling law, inclined chute results were compared with results from other flow configurations: the simple shear and the vertical chute flow. Results are shown in Figure 6. It is first necessary to note that vertical chute simulations, which were steady but not periodic (particles were recirculated at the free surface and velocity was controlled by fixing the velocity of a bottom layer), were locally averaged in space but globally averaged only in time. Therefore each simulation produced a series of values of slip velocity, stresses et cetera, obtained as a time average of the given variable at a certain position at the wall. In order to help comprehension, vertical chute results were therefore represented with error bars in γdp versus rescaled effective wall friction coefficient µw µpw , for (•) regular and (•) elongated pentagons, for inclined chute flow. Lines are best fits described in the text. Reproduced from [8]. figure 6, while for the other simulations each point corresponds to a simulation. A strong result was found: for high enough friction, µ w /µ pw < 0.75, the scaling law appears to be independent of the geometry. For µ w /µ pw > 0.75, simple shear results agree fairly well with inclined chute results, however strong deviations appear in vertical chute results, characterized also by a larger variance of the results.

Scaling universality

Many instructive issues can be extracted from the numerical results. First, it was found that the scaling law for the slip length preserved the same qualitative features among different geometries. In particular, for all the geometries the behavior is consistent in its limits with simple sliding: the behavior tends to zero slip length for high friction, i.e. µ w /µ pw → 0), and to zero shear with a finite velocity for low enough friction. Then, between the two limits ( i.e. 0 < µ w /µ pw < 1), slip velocity and shear rate take generally finite values, with an increasing slip length for increasing µ w /µ pw . A relation between two dimensionless numbers, v slip γdp and µ w /µ pw , was proposed to describe this intermediate be- havior. The same functional form was found to hold for different particle shapes, with more irregular particles showing lower slip length values.

For high enough wall friction, the scaling was found to be independent on the geometrical configuration. This suggests that a road for a universal scaling of wall slip has been traced. The deviations observed in vertical chute simulations need to be explained, and this should be probably done by introducing other dimensionless numbers, such as the inertial number, the normal stress ratio, and the solid fraction in the tractation.

Discussion and conclusions

In this work, at first experiments were presented in order to study the main features of wall slip in dense granular flows. Slip was characterized with a dimensionless parameter, the rescaled slip length v slip γdp . While a rather complex picture was discovered, the major trends were identified: the joint effects of internal friction, wall roughness and flowrate were highlighted. In order to obtain a more refined picture, 2D discrete numerical simulations of polygonal poarticles were carried out in different flow configurations. First, results tend to confirm the theoretical framework firstly proposed in [3]: dense flows of granular materials are characterised by force chains which are continuously breaking and forming. Local, ephemeral force imbalances are therefore to be found in these flows. These imbalances which characterize the dynamics of the force network may cause the tangential forces to be locally higher than the sliding threshold, even if the average tangential force is lower than the average sliding threshold. The kinematics of particles in contact with the wall will be therefore characterised by a succession of slip events, which will globally produce a finite average slip velocity. This framework, applied to the numerical results, allowed to hypothesize that the dimensionless slip length is a function of the ratio between the effective wall friction coefficient µ w = τ /σ w and the particlewall friction coefficient µ pw . The framework appeared to be consistent among different geometrical configurations, though some deviations were found (particularly for vertical chute results) which strongly need further clarification. Future work will deal with testing of the relevant scaling laws in 3D simulations; in parallel, a plan of experimental tests coupling measurements of velocity profiles and wall stresses is under development.

Fig. 1 (

 1 Fig. 1 (a) Sketch of the experimental setup with the imaging arrangement, (b) Sketch of the typical velocity profile obtained in dense granular flow in vertical chutes.

Fig. 2

 2 Fig. 2 Photographs of the materials used in the experiments (a) TAED 600-800 (b) TAED 800-1000 (c) TAED 1000-1410 (d) Steel shots (e) Cellulose (f) Steel grit 850-1000 (g) Steel grit 1000-1180 (h) Calcium carbonate 600-710 (i) Calcium carbonate 800-1000 (j) Calcium carbonate 1000-1180.

Fig. 3

 3 Fig. 3 Dimensionless slip length v slip γdp versus relative roughness d R /dp, for (•) class A and ( ) class B materials (see explanation in the text). The symbols represent averages of the slip length, while the bars represent the span of the data, from minimum to maximum value.

Fig. 4

 4 Fig. 4 Flow configurations used in the numerical simulations: (a) inclined chute, (b) vertical chute, (c) simple shear flow.

  parameters A = 2.2, B = 0.42 for elongated and A = 4.23 and B = 0.33 for regular pentagons. The data as well as the fitting functions are shown in Figure 5.

Fig. 6

 6 Fig. 6 Dimensionless slip parameter v slip γdp versus rescaled effective wall friction coefficient µw µpw , for regular particles, in different flow configurations: (•) inclined chute flow (Figure 5), ( ) vertical chute flow, and ( ) simple shear flow. The solid line is the best fit for inclined chute flow of the scaling law described in the text.

Table 1

 1 Properties of the materials used for experiments.

	φ	φw †	φw ‡

Material

sieve size range (µm) ρ b (kg/m 3 ) † 40 grit sandpaper, ‡ 120 grit sandpaper.

Table 2

 2 Parameters defining the numerical simulations.

	Flow geometry		Dimension		Particle shape	Number of	Wall Inertial number	Particle-wall friction
								particles N p	I =	γd p √ p/ρ p	coefficient µ pw
	Inclined chute[8]		2D		Regular pentagons	5000	2 × 10 -2 -10 -1	0.63-1.08
	Inclined chute[8]		2D	Elongated pentagons	5000	5 × 10 -3 -1.5 × 10 -1	0.63-1.08
	Vertical chute		2D		Regular pentagons	4500-9000	10 -3 -10 -1	0.4-1.2
	Simple shear		2D		Regular pentagons	4000	10 -2 -10 -1	0.47-1.1
		8
		6
	p
	v slip / γd	2 4		actual behavior			steady sliding
						simple sliding behavior
		0			no-slip
		0.4	0.5	0.6	0.7	0.8	0.9	1.0
					µ w /µ pw
	Fig. 5 Dimensionless slip parameter	v slip

ARTONI, Riccardo, SANTOMASO, Andrea, 2014, Effective wall slip in chutes and channels: experiments and discrete element simulations, Granular Matter, 16, 3, SPRINGER, pp.377-382, DOI: 10.1007/s10035-013-0431-y

Acknowledgements RA wishes to thank P. Richard for helpful discussions.