Computational Complexity

Advancement in cognitive science depends, in part, on doing some occasional ‘theoretical housekeeping’. We highlight some conceptual confusions lurking in an important attempt at explaining the human capacity for rational or coherent thought: Thagard & Verbeurgt’s computational-level model of humans’ capacity for making reasonable and truth-conducive abductive inferences (1998; Thagard, 2000). Thagard & Verbeurgt’s model assumes that humans make such inferences by computing a coherence function (f_coh), which takes as input representation networks and their pair-wise constraints and gives as output (...) a partition into accepted (A) and rejected (R) elements that maximizes the weight of satisfied constraints. We argue that their proposal gives rise to at least three difficult problems. (shrink)

From algorithmic information theory (and using notions of algorithmic thermodynamics), we introduce *feasible mathematics* as distinct from *universal mathematics*. Feasible mathematics formalizes the intuition that theorems with very long proofs are unprovable within the context of limited computing resources. It is formalized by augmenting the standard construction of Omega with a conjugate-pair that suppresses programs with long runtimes. The domain of the new construction defines feasible mathematics.

We report a mathematical construction that is autological, universal and tautological. The autological property allows the derivation of the laws of physics from the construction, while the other two properties explain why the construction is universally and necessarily applicable to the world. The construction can explain the World at its most fundamental level up to and including the derivation of the familiar laws of physics. It is formulated as a statistical ensemble of feasible mathematics (an algorithmic information theory analog to (...) statistical physics) and its domain is the set of all analytical statements of logic ---here they take the role of the permissible facts of the world. The familiar laws of physics are emergent from the ensemble as entropic laws; this includes special relativity, general relativity, dark energy, the Schrödinger equation, the Dirac equation, quantum field theory, the speed of light as a maximal speed, and the space-time background. Furthermore, the construction provides tentative solutions in regard to the quantum measurement problem, the unification of physics and the arrow of time. In this context, the laws of physics are interpreted as the limits applicable to the feasible verification of the elements of the set of all analytical facts (they limit the actual facts of the world). The scope is universal (applies to the whole world), it is constructed tautologically (is irrefutable) and it is autological (allows the derivation of the laws of physics) ---thus, it is a tentative final theory. (shrink)

Many cognitive scientists, having discovered that some computational-level characterization f of a cognitive capacity φ is intractable, invoke heuristics as algorithmic-level explanations of how cognizers compute f. We argue that such explanations are actually dysfunctional, and rebut five possible objections. We then propose computational-level theory revision as a principled and workable alternative.

Hilbert's ε-calculus is based on an extension of the language of predicate logic by a term-forming operator εx. Two fundamental results about the ε-calculus, the first and second epsilon theorem, play a rôle similar to that which the cut-elimination theorem plays in sequent calculus. In particular, Herbrand's Theorem is a consequence of the epsilon theorems. The paper investigates the epsilon theorems and the complexity of the elimination procedure underlying their proof, as well as the length of Herbrand disjunctions of existential (...) theorems obtained by this elimination procedure. (shrink)

Here, by introducing a version of “Unexpected hanging paradox” first we try to open a new way and a new explanation for paradoxes, similar to liar paradox. Also, we will show that we have a semantic situation which no syntactical logical system could support it. Finally, we propose a claim in Theory of Computation about the consistency of this Theory. One of the major claim is:Theory of Computation and Classical Logic leads us to a contradiction.

We analyse the computational complexity of three problems in judgment aggregation: (1) computing a collective judgment from a profile of individual judgments (the winner determination problem); (2) deciding whether a given agent can influence the outcome of a judgment aggregation procedure in her favour by reporting insincere judgments (the strategic manipulation problem); and (3) deciding whether a given judgment aggregation scenario is guaranteed to result in a logically consistent outcome, independently from what the judgments supplied by the individuals are (the (...) problem of the safety of the agenda). We provide results both for specific aggregation procedures (the quota rules, the premisebased procedure, and a distance-based procedure) and for classes of aggregation procedures characterised in terms of fundamental axioms. (shrink)

I argue that considerations about computational complexity show that all finite agents need characteristics like those that have been called epistemic virtues. The necessity of these virtues follows in part from the nonexistence of shortcuts, or efficient ways of finding shortcuts, to cognitively expensive routines. It follows that agents must possess the capacities – metavirtues –of developing in advance the cognitive virtues they will need when time and memory are at a premium.

In this paper we give some formal examples of ideas developed by Penco in two papers on the tension inside Frege's notion of sense (see Penco 2003). The paper attempts to compose the tension between semantic and cognitive aspects of sense, through the idea of sense as proof or procedure – not as an alternative to the idea of sense as truth condition, but as complementary to it (as it happens sometimes in the old tradition of procedural semantics).