Download options PhilArchive copy. Configure custom resolver. Minds, Brains, and Programs. John R. Searle - - Behavioral and Brain Sciences 3 3 The Rediscovery of the Mind. John Searle - - In John Heil ed. Oxford University Press. Modeling Bounded Rationality. A Simplicity Criterion for Physical Computation. Quantum Computing. Regina E. The Philosophy of Computer Science.
Raymond Turner - - Stanford Encyclopedia of Philosophy. Computational Model Theory: An Overview. Open Preview See a Problem? Details if other :.
Thanks for telling us about the problem. Return to Book Page. Get A Copy. More Details Edition Language. Friend Reviews. To see what your friends thought of this book, please sign up.
Lists with This Book. This book is not yet featured on Listopia. Add this book to your favorite list ». Community Reviews. Showing Average rating 4. It thus follows that at least one of the first four displayed inclusions must be proper and also at least one of the third, fourth, or fifth. Figure 2. Inclusion relationships among major complexity classes.
At the moment, however, this is all that is currently known — i. Providing unconditional proofs of these claims remains a major unfulfilled goal of complexity theory. For instance, the following is often described as the single most important open question in all of theoretical computer science:. The significance of Open Question 1 as well as several additional unresolved questions about the inclusion relations among other complexity classes will be considered at greater length in Section 4.
Having now introduced some of the major classes studied in complexity theory, we next turn to the question of their internal structure. This can be studied using the notions of the reducibility of one problem to another and of a problem being complete for a class. The concepts of reduction and completeness were originally introduced in computability theory. Therein a number of different definitions of reduction are studied, of which many-one and Turing reducibility are the most familiar see, e.
Analogues of both of these have been studied in complexity theory under the names polynomial time many-one reducibility — also known as Karp reducibility Karp — and polynomial time Turing reducibility — also known as Cook reducibility Cook For simplicity we will consider only the former here. Definition 3. But since most mathematically natural problems bear no relationship to Turing machines, it is by no means obvious that such reductions exist.
In order to demonstrate Theorem 3. The proof of Theorem 3. In light of this, Theorem 3. The reductions required to show the completeness of these problems typically require the construction of what has come to be known as a gadget — i. Figure 3. Thus although the problems listed above are seemingly unrelated in the sense that they concern different kinds of mathematical objects — e. As long as Open Question 1 is answered in the positive — i. As we are now about to see, however, they are by no means the hardest problems studied by complexity theorists.
In fact, the following is another fundamental unresolved question in contemporary complexity theory:. It is widely believed that like Open Question 1, Open Question 2 has an affirmative answer. But this class also contains some problems which are not currently known to be feasibly decidable. This follows because prime factorizations are unique unlike, e. For recall that it is a consequence of Theorem 3. Hence problems complete for these classes can currently be classified as infeasible regardless of how Open Question 1 is resolved.
Such problems include several sub-cases of the decision problem for first-order logic which will be considered in Section 4. We may now define the problem. This result suggests that there is a close connection between problems which can be decided using unbounded time but a feasible amount of memory space and those which could be solved if we were able to answer certain kinds of existential or universal queries in a single step using a bounded number of alternations between the two kinds of queries.
This observation can be used to give an alternative characterization of several of the complexity classes we have considered. Proposition 3. It follows immediately from Proposition 3. But whereas it can be shown by a standard diagonal argument that the arithmetic hierarchy does not collapse, the following are also currently unresolved questions of fundamental importance:. Subject to similar modification to the end game rules, analogous results have also been obtained for chess Fraenkel and Lichtenstein and checkers Robson This observation provides part of the reason why it is currently expected that the answer to Open Question 3a is positive.
A related observation bears on the status of Open Question 3b. Comprehensive consideration of the diversity of these classes is beyond the scope of the current survey. This model is a variant of the conventional RAM model described in Section 2. Each program also controls a separate processor with its own program counter and accumulator. The processors operate in parallel and can write to a common block of registers, adopting some policy for resolving with conflicts.
In this way, a PRAM machine can recruit more processors to operate on larger inputs, although the number of processors employed must be fixed uniformly in the size of the input. It has long been known that certain problems — e. But this observation would still be of little practical significance if the algorithms in question achieved such speed up only at the cost of having to employ exponentially many processors relative to the size of their inputs.
For in this case it seems that we would have little hope of building a computing device on which they could be concretely implemented. Greenlaw, Hoover, and Ruzzo The current consensus is that like Open Questions 1—3, Open Question 4 will also be answered in the positive. Another active area of research in complexity theory concerns classes defined in terms of probabilistic models of computation.
Instances of such models are assumed to have access to some genuine source of randomness — e. As we have seen, however, non-deterministic Turing machines cannot be employed as a practical model of probabilistic computation. Thus although it might at first seem plausible that the ability to make random choices during the course of a computation allows us to practically solve certain problems which resist efficient deterministic algorithms, it is again an open problem whether this is true.
Such a model can be roughly characterized as a device which makes use of quantum-mechanical phenomena such as entanglement or interference to perform operations on data represented by sequences qubits — i. Several algorithms have been discovered which can be implemented on such devices which run faster than the best known classical algorithms for the same problem.
There is also considerable controversy as to whether it will prove possible to construct physical realizations of such models which are sufficiently robust to reliably solve instances of problems which cannot currently be solved using classical hardware. Nonetheless, quantum computation is a very active area of research at present.
There has to date been surprisingly little philosophical engagement with computational complexity theory. Although several questions which have their origins in computability theory — e. And despite ongoing interest in logical knowledge and resource bounded reasoning, fields such as epistemology, decision theory, and social choice theory have only recently begun to make use of complexity-theoretic concepts and results.
This section will attempt to bridge some of these gaps by highlighting connections between computational complexity and traditional topics in logic and philosophy. The appreciation of complexity theory outside of theoretical computer science is largely due to the notoriety of open questions such as 1—4.
Along with long standing unresolved questions from pure and applied mathematics such as the Riemann Hypothesis and the Hodge Conjecture, it is the subject of a major prize competition — i.
It is also frequently the focus of survey articles and popular expositions — e. Sipser , Fortnow , and Fortnow Our intuitions strongly reflect the fact that the former problems in such pairs seem more difficult than the latter. Building on this observation, several more recent commentators e.
For note that although this statement originates in theoretical computer science, it may be easily formulated as statements about natural numbers. A familiar example is the method of diagonalization, as employed in the proof of the undecidability of the classical Halting Problem from which it follows that the recursive languages are properly included in the recursively enumerable ones.
Several programs for separating complexity classes have recently been explored using techniques from circuit complexity e. Razborov and Rudich , proof theory e. Buss , and algebraic geometry e. Mulmuley and Sohoni However, the current consensus e. Fortnow is that these approaches are still in need of substantial refinement or that genuinely new methods will be required in order to yield the desired separations.
We have seen that logic provides many examples of problems which are studied in complexity theory. Of these, the most often considered are satisfiability , validity , and model checking. In this case, the model checking problem is only considered for finite structures which we must also assume are encoded as finite strings — e. And in cases where a logic is standardly characterized proof theoretically rather than semantically — i. In such cases, the satisfiability and model checking problems are generally not considered.
A number of results are summarized in Table 1, focusing on systems surveyed in other articles in this encyclopedia. Table 1. The complexity of the satisfiability, validity, and model checking problems for some common logics. Although these problems are characterized in terms of the semantics for propositional logic, certain questions about its proof theory may also be addressed using techniques from complexity theory. Each of these systems may be shown to be sound and complete for propositional validity — i.
Theorem 4. A positive answer was obtained by Haken for the system known as resolution on which many automated theorem-provers are based. The formula. From this it follows that resolution is not polynomially bounded. One subsequent direction of research in proof complexity has been to identify additional proof systems for which PHP or related combinatorial principles are also hard. Another connection between logic and computational complexity is provided by the subject known as descriptive complexity theory.
Descriptive complexity begins with the observation that since computational problems are comprised by finite combinatorial objects e. These are treated semantically as logical symbols. Descriptive characterizations have been obtained for many of the major complexity classes considered in Section 3 , several of which are summarized in Table 2. Fagin established the following:. This result provided one of the first machine independent characterizations of an important complexity class — i.
In order to characterize additional classes, other means of extending the expressive capacity of first-order logic must be considered such as adding least fixed point or transitive closure operators. Immerman , p. Taken in conjunction with Theorem 4. On the other hand, the restriction to ordered structures in the formulation of Theorem 4. Table 2. Descriptive characterization of complexity classes. Another connection between logic and computational complexity is provided by first-order arithmetical theories which are similar in form to familiar systems such as Primitive Recursive Arithmetic and Peano arithmetic.
Connections between formal arithmetic and computability theory have been known since the s — e. From the s onwards, a number of similar results have been obtained which link the levels of the Polynomial Hierarchy to a class of first-order theories collectively known as bounded arithmetics.
In the course of studying the relationship between arithmetic and complexity theory, it is often useful to consider functions in addition to sets. Definition 4. Like Theorems 4. Recall, however, that Cobham was working at a time when the mathematical status of the notion of feasibility was still under debate.
Relative to the standards discussed in Section 1. This suggests that feasibility is also preserved when a function is defined by limited recursion on notation. But it may also be shown that this theory does not prove the totality of exponentiation under this or any other definition in the following sense:. Since terms in the language of arithmetic are polynomials with positive coefficients, it follows from Theorem 4. In particular, exponentiation is not provably total in this theory.
Buss presented a sequence of first-order theories. We also define the following induction schemas:. It follows from Theorem 4. In parallel to Theorem 4. The most direct links between philosophy of mathematics and computational complexity theory have thus far arisen in the context of discussions of the view traditionally known as strict finitism. Presuming that such expressions denote at all, Yessenin-Volpin contended that they cannot be taken to describe what he referred to as feasible numbers — i.
On this basis, he outlined a foundational program wherein feasibility is treated as a basic notion and traditional arguments in favor of the validity of mathematical induction and the uniqueness of the natural number series are called into question.
Antecedents for such a view may be found in e. Bernays , van Dantzig , and Wang Recall that one tenet of the traditional form of finitism associated with the Hilbert Program is that the natural numbers should not be conceived as comprising a completed infinite totality.
Strict finitists are sometimes described as going one step further than this and actively denying that there are infinitely many natural numbers. Topics from this paper. Computational complexity theory Computational theory of mind Quantum mechanics Computation. Artificial general intelligence Mathematical induction Computational problem Randomness. Rationality Computable function Hume programming language.
Paper Mentions. Blog Post. Theory, Evolution, and Games Group. What can theoretical computer science offer biology? Monoids, weighted automata and algorithmic philosophy of science. Citation Type. Has PDF. Publication Type. More Filters. Tractability and the computational mind. View 1 excerpt, cites background.
0コメント