Computational Complexity

As a philosophy of mathematics, strict finitism has been traditionally concerned with the notion of feasibility, defended mostly by appealing to the physicality of mathematical practice. This has led the strict finitists to influence and be influenced by the field of computational complexity theory, under the widely held belief that this branch of mathematics is concerned with the study of what is “feasible in practice”. In this paper, I survey these ideas and contend that, contrary to popular belief, complexity theory (...) is not what the ultrafinitists think it is, and that it does not provide a theoretical framework in which to formalize their ideas —at least not while defending the material grounds for feasibility. I conclude that the subject matter of complexity theory is not proving physical resource bounds in computation, but rather proving the absence of exploitable properties in a search space. (shrink)

The philosophy of mind is traditionally concerned with the study of mental processes, language, the representation of knowledge and the relation of the mind shares with the body; computational complexity theory is related to the classification of computationally solvable problems (be it via execution time, storage requirements, etc...). While there are well-established links between computer science in general & the philosophy of mind, many possible solutions to traditional problems in the philosophy of mind have not yet been analyzed from the (...) more specific lens of computational complexity theory. In his paper "Why Philosophers Should Care about Computational Complexity", Scott Aaronson argues that many conventional theories of epistemology & mind implicitly make the presupposition of omniscience (by supposing that knowing base facts means a knower necessarily understands derivative facts) - he proposes that computational complexity theory could explain why this is not the case. In this paper, I argue for a theory of mental representation & epistemology compatible with Aaronson's observations on complexity theory, overcoming that presupposition of omniscience. (shrink)

Throughout this paper, we are trying to show how and why our Mathematical frame-work seems inappropriate to solve problems in Theory of Computation. More exactly, the concept of turning back in time in paradoxes causes inconsistency in modeling of the concept of Time in some semantic situations. As we see in the first chapter, by introducing a version of “Unexpected Hanging Paradox”,first we attempt to open a new explanation for some paradoxes. In the second step, by applying this paradox, it (...) is demonstrated that any formalized system for the Theory of Computation based on Classical Logic and Turing Model of Computation leads us to a contradiction. We conclude that our mathematical frame work is inappropriate for Theory of Computation. Furthermore, the result provides us a reason that many problems in Complexity Theory resist to be solved.(This work is completed in 2017 -5- 2, it is in vixra in 2017-5-14, presented in Unilog 2018, Vichy). (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.

The reason ability of considering time as a fuzzy concept is demonstrated in [7],[8]. One of the major questions which arise here is the new definitions of Complexity Classes. In [1],[2],…,[11] we show why we should consider time a fuzzy concept. It is noticeable to mention that that there were many attempts to consider time as a Fuzzy concept, in Philosophy, Mathematics and later in Physics but mostly based on the personal intuition of the authors or as a style of (...) Fuzzifying different various of the concepts. Consequently, fuzzifying time doesn’t go to be popular. In the new attempts we are trying to show why we are somewhat forced to consider time as a Fuzzy concept. It is mostly based on the “Unexpected Hanging Paradox” introduced by a Swedish Mathematician Lennart Ekbom. Our question is:” what will be the impact of it in Theory of Computation and Physics?”. Here, we discuss about the impact of fuzzifying time on Theory of Computation. (shrink)

Quantum computing is of high interest because it promises to perform at least some kinds of computations much faster than classical computers. Arute et al. 2019 (informally, “the Google Quantum Team”) report the results of experiments that purport to demonstrate “quantum supremacy” – the claim that the performance of some quantum computers is better than that of classical computers on some problems. Do these results close the debate over quantum supremacy? We argue that they do not. In the following, we (...) provide an overview of the Google Quantum Team’s experiments, then identify some open questions in the quest to demonstrate quantum supremacy. (shrink)

FDE is a logic that captures relevant entailment between implication-free formulae and admits of an intuitive informational interpretation as a 4-valued logic in which “a computer should think”. However, the logic is co-NP complete, and so an idealized model of how an agent can think. We address this issue by shifting to signed formulae where the signs express imprecise values associated with two distinct bipartitions of the set of standard 4 values. Thus, we present a proof system which consists of (...) linear operational rules and only two branching structural rules, the latter expressing a generalized rule of bivalence. This system naturally leads to defining an infinite hierarchy of tractable depth-bounded approximations to FDE. Namely, approximations in which the number of nested applications of the two branching rules is bounded. (shrink)

Is human free will compatible with the natural laws of the universe? To “compatibilists” who see free actions as emanating from the wants and reasons of human agents, free will looks perfectly plausible. However, “incompatibilists” claim to see the more ultimate sources of human action. The wants and reasons of agents are said to be caused by physical processes which are themselves mere natural results of the previous state of the world and the natural laws which govern it. This paper (...) argues that the incompatibilists make a mistake in appealing to such non-agent sources of human action. They fail to realize that free will may exist at one scale, but not at the scales where they look. When free will is considered from the correctly scaled perspective, it does seem compatible with determinism and natural laws. (shrink)

Bedau's influential (1997) account analyzes weak emergence in terms of the non-derivability of a system’s macrostates from its microstates except by simulation. I offer an improved version of Bedau’s account of weak emergence in light of insights from information theory. Non-derivability alone does not guarantee that a system’s macrostates are weakly emergent. Rather, it is non-derivability plus the algorithmic compressibility of the system’s macrostates that makes them weakly emergent. I argue that the resulting information-theoretic picture provides a metaphysical account of (...) weak emergence rather than a merely epistemic one. (shrink)

Two strategies to infinity are equally relevant for it is as universal and thus complete as open and thus incomplete. Quantum mechanics is forced to introduce infinity implicitly by Hilbert space, on which is founded its formalism. One can demonstrate that essential properties of quantum information, entanglement, and quantum computer originate directly from infinity once it is involved in quantum mechanics. Thus, thеse phenomena can be elucidated as both complete and incomplete, after which choice is the border between them. A (...) special kind of invariance to the axiom of choice shared by quantum mechanics is discussed to be involved that border between the completeness and incompleteness of infinity in a consistent way. The so-called paradox of Albert Einstein, Boris Podolsky, and Nathan Rosen is interpreted entirely in the same terms only of set theory. Quantum computer can demonstrate especially clearly the privilege of the internal position, or “observer”, or “user” to infinity implied by Henkin’s proposition as the only consistent ones as to infinity. (shrink)

A practical viewpoint links reality, representation, and language to calculation by the concept of Turing (1936) machine being the mathematical model of our computers. After the Gödel incompleteness theorems (1931) or the insolvability of the so-called halting problem (Turing 1936; Church 1936) as to a classical machine of Turing, one of the simplest hypotheses is completeness to be suggested for two ones. That is consistent with the provability of completeness by means of two independent Peano arithmetics discussed in Section I. (...) Many modifications of Turing machines cum quantum ones are researched in Section II for the Halting problem and completeness, and the model of two independent Turing machines seems to generalize them. Then, that pair can be postulated as the formal definition of reality therefore being complete unlike any of them standalone, remaining incomplete without its complementary counterpart. Representation is formal defined as a one-to-one mapping between the two Turing machines, and the set of all those mappings can be considered as “language” therefore including metaphors as mappings different than representation. Section III investigates that formal relation of “reality”, “representation”, and “language” modeled by (at least two) Turing machines. The independence of (two) Turing machines is interpreted by means of game theory and especially of the Nash equilibrium in Section IV. Choice and information as the quantity of choices are involved. That approach seems to be equivalent to that based on set theory and the concept of actual infinity in mathematics and allowing of practical implementations. (shrink)

A set theory model of reality, representation and language based on the relation of completeness and incompleteness is explored. The problem of completeness of mathematics is linked to its counterpart in quantum mechanics. That model includes two Peano arithmetics or Turing machines independent of each other. The complex Hilbert space underlying quantum mechanics as the base of its mathematical formalism is interpreted as a generalization of Peano arithmetic: It is a doubled infinite set of doubled Peano arithmetics having a remarkable (...) symmetry to the axiom of choice. The quantity of information is interpreted as the number of elementary choices (bits). Quantum information is seen as the generalization of information to infinite sets or series. The equivalence of that model to a quantum computer is demonstrated. The condition for the Turing machines to be independent of each other is reduced to the state of Nash equilibrium between them. Two relative models of language as game in the sense of game theory and as ontology of metaphors (all mappings, which are not one-to-one, i.e. not representations of reality in a formal sense) are deduced. (shrink)

Despite their success in describing and predicting cognitive behavior, the plausibility of so-called ‘rational explanations’ is often contested on the grounds of computational intractability. Several cognitive scientists have argued that such intractability is an orthogonal pseudoproblem, however, since rational explanations account for the ‘why’ of cognition but are agnostic about the ‘how’. Their central premise is that humans do not actually perform the rational calculations posited by their models, but only act as if they do. Whether or not the problem (...) of intractability is solved by recourse to ‘as if’ explanations critically depends, inter alia, on the semantics of the ‘as if’ connective. We examine the five most sensible explications in the literature, and conclude that none of them circumvents the problem. As a result, rational ‘as if’ explanations must obey the minimal computational constraint of tractability. (shrink)

Quantum computer is considered as a generalization of Turing machine. The bits are substituted by qubits. In turn, a "qubit" is the generalization of "bit" referring to infinite sets or series. It extends the consept of calculation from finite processes and algorithms to infinite ones, impossible as to any Turing machines (such as our computers). However, the concept of quantum computer mets all paradoxes of infinity such as Gödel's incompletness theorems (1931), etc. A philosophical reflection on how quantum computer might (...) implement the idea of "infinite calculation" is the main subject. (shrink)

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)

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.

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

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)

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)

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.

A computational theory is developed that explains how line drawings of polyhedral objects can be interpreted rapidly and in parallel at early levels of human vision. The key idea is that a time-limited process can correctly recover much of the three-dimensional structure of these objects when split into concurrent streams, each concerned with a single aspect of scene structure.

In a series of articles we try to show the need of a novel Theory for Theory of Computation based on considering time as a Fuzzy concept. Time is a central concept In Physics. First we were forced to consider some changes and modifications in the Theories of Physics. In the second step and throughout this article we show the positive Impact of this modification on Theory of Computation and Complexity Theory to rebuild it in a more successful and fruitful (...) approach. We call this novel Theory TC*. (shrink)

Here, we try to build the structure of a Theory of computation based on considering time as a fuzzy concept. Actually, there are some reasons to consider time as a fuzzy concept. In this article, we don’t go to this side but we remind that Brower and Husserl ideas about the concept of time were similar [14]. Throughout this article, we present the Theory of Computation with Fuzzy Time. Considering the classical definition of Turing Machine we change and modify the (...) concept of Time to Fuzzy time. We call this new Theory TC* and this type of computation “Fuzzy time Computation”. We have relatively large number of fundamental unsolved problems in Complexity Theory. In the new Theory some of the major obstacles and unsolved problems are solved. It should be mentioned that in this article, we consider fuzzy number a symmetric one. The point about the symmetry is in the proof of Lemma 3, although we are able to generalize it. More specifically, we define the new classes of complexity Theory, P*, NP*, BPP* in TC* analogues to the definitions P, NP, BPP as their natural substituted definition. We show P*≠ NP*, P*= BPP*. Finally, we have Theorem 4, P≠NP . (shrink)

در تکوین نظریه محاسبات از اوایل قرن بیستم پارادکسها و خود ارجاعی نقش ویژه ای را بازی کرده اند. هر چند نظریه محاسبات عام بر اساس تعریف ماشین تورینگ، فرض تورینگ_چرچ و کاربردهای آن بنا شده ،اما از همان ابتدا تا به امروز منطق و حوزه های مختلف این علم در ارتباط تنگاتنگ با این تیوری و در ابتدا نظریه محاسبات خاص بوده و این ارتباط روز به روز گسترده و گسترده تر گشته است. از تاثیر پارادوکس دروغگو و پارادکس (...) بری در تمایز میان مفهوم محاسبه پذیر و محاسبه پذیر شمارایانه، قضایای گودل و قضیه چیتین همه جا شاهد این تاثیر و تاثر متقابل هستیم. در این مقال می خواهیم بعد از معرفی اجمالی مطالب باال، تاثیر یک پارادوکس دیگر، پارادوکس اعدام غیر منتظره، را بر این نظریه بررسی نماییم. (shrink)