We consider the relationship between the computational complexity classes NP and EL . Taking into account the inclusion or incomparability of these classes, the existence or nonexistence of immune sets in their differences, and the existence or nonexistence of sparse sets in the differences, there are exactly 24 different cases for their relationship. We show that 16 cases are impossible in the real nonrelativized world as well as in any relativized world. Each of the remaining 8 cases is realizable in (...) appropriate relativized worlds. Further we examine which of the 8 cases is most probably for a random oracle. (shrink)

Relations between discrete and continuous complexity models are considered. The present paper is devoted to combine both models. In particular we analyze the 3-Satisfiability problem. The existence of fast decision procedures for this problem over the reals is examined based on certain conditions on the discrete setting. Moreover we study the behaviour of exponential time computations over the reals depending on the real complexity of 3-Satisfiability. This will be done using tools from complexity theory over the integers.

The intuition guiding the de…nition of computation has shifted over time, a process that is re‡ected in the changing formulations of the Church-Turing thesis. The theory of computation began with logic and gradually moved to the capacity of …nite automata. Consequently, modern computer models rely on general physical principles, with quantum computers representing the extreme case. The paper discusses this development, and the challenges to the Church-Turing thesis in its physical form, in particular, Kieu’s quantum computer and relativistic hyper-computation. Finally, (...) the robustness of the boundary between polynomial and exponential time complexity is considered in connection with quantum computers and quantum information theory. (shrink)

Ko, K., On the computational complexity of integral equations, Annals of Pure and Applied Logic 58 201–228. The computational complexity of Volterra integral equations of the second kind and of the first kind is investigated. It is proved that if the kernel functions satisfy the Lipschitz condition, then the solutions of Volterra equations of the second kind are polynomial-space computable. If, one the other hand, the kernel functions only satisfy the local Lipschitz condition with the Lipschitz constants growing in an (...) exponential rate, then the solutions could be exponential-time hard. We identify a class of Volterra equations of the first kind that can be converted to Volterra equations of the second kind satisfying the local Lipschitz condition. The complexity of the solutions of these equations is also proved to be exponential-time hard. (shrink)

Combining physics, mathematics and computer science, quantum computing and its sister discipline of quantum information have developed in the past few decades from visionary ideas to two of the most fascinating areas of quantum theory. General interest and excitement in quantum computing was initially triggered by Peter Shor (1994) who showed how a quantum algorithm could exponentially “speed-up” classical computation and factor large numbers into primes far more efficiently than any (known) classical algorithm. Shor’s algorithm was soon followed by several (...) other algorithms that aimed to solve combinatorial and algebraic problems, and in the years since theoretical study of quantum systems serving as computational devices has achieved tremendous progress. Common belief has it that the implementation of Shor’s algorithm on a large scale quantum computer would have devastating consequences for current cryptography protocols which rely on the premise that all known classical worst-case algorithms for factoring take time exponential in the length of their input (see, e.g., Preskill 2005). Consequently, experimentalists around the world are engaged in attempts to tackle the technological difficulties that prevent the realisation of a large scale quantum computer. But regardless whether these technological problems can be overcome (Unruh 1995; Ekert and Jozsa 1996; Haroche and Raimond 1996), it is noteworthy that no proof exists yet for the general superiority of quantum computers over their classical counterparts. -/- The philosophical interest in quantum computing is manifold. From a social-historical perspective, quantum computing is a domain where experimentalists find themselves ahead of their fellow theorists. Indeed, quantum mysteries such as entanglement and nonlocality were historically considered a philosophical quibble, until physicists discovered that these mysteries might be harnessed to devise new efficient algorithms. But while the technology for harnessing the power of 50–100 qubits (the basic unit of information in the quantum computer) is now within reach (Preskill 2018), only a handful of quantum algorithms exist, and the question of whether these can truly outperform any conceivable classical alternative is still open. From a more philosophical perspective, advances in quantum computing may yield foundational benefits. For example, it may turn out that the technological capabilities that allow us to isolate quantum systems by shielding them from the effects of decoherence for a period of time long enough to manipulate them will also allow us to make progress in some fundamental problems in the foundations of quantum theory itself. Indeed, the development and the implementation of efficient quantum algorithms may help us understand better the border between classical and quantum physics (Cuffaro 2017, 2018a; cf. Pitowsky 1994, 100), and perhaps even illuminate fundamental concepts such as measurement and causality. Finally, the idea that abstract mathematical concepts such as computability and complexity may not only be translated into physics, but also re-written by physics bears directly on the autonomous character of computer science and the status of its theoretical entities—the so-called “computational kinds”. As such it is also relevant to the long-standing philosophical debate on the relationship between mathematics and the physical world. (shrink)

1. The Physical Church-Turing Thesis. Physicists often interpret the Church-Turing Thesis as saying something about the scope and limitations of physical computing machines. Although this was not the intention of Church or Turing, the Physical Church Turing thesis is interesting in its own right. Consider, for example, Wolfram’s formulation: One can expect in fact that universal computers are as powerful in their computational capabilities as any physically realizable system can be, that they can simulate any physical system . . . (...) No physically implementable procedure could then shortcut a computationally irreducible process. (Wolfram 1985) Wolfram’s thesis consists of two parts: (a) Any physical system can be simulated (to any degree of approximation) by a universal Turing machine (b) Complexity bounds on Turing machine simulations have physical significance. For example, suppose that the computation of the minimum energy of some system of n particles takes at least exponentially (in n) many steps. Then the relaxation time of the actual physical system to its minimum energy state will also take exponential time. (shrink)

The aim of this paper is to investigate the ascription of probabilities in a causal model of an episode in the history of science. The aim of such a quantitative approach is to allow the implementation of the causal model in a computer, to run simulations. As an example, we look at the beginning of the science of magnetism, “explaining” — in a probabilistic way, in terms of a single causal model — why the field advanced in China but not (...) in Europe (the difference is due to different prior probabilities of certain cultural manifestations). Given the number of years between the occurrences of two causally connected advances X and Y, one proposes a criterion for stipulating the value pY/X of the conditional probability of an advance Y occurring, given X. Next, one must assume a specific form for the cumulative probability function pY/X(t), which we take to be the time integral of an exponential distribution function, as is done in physics of radioactive decay. Rules for calculating the cumulative functions for more than two events are mentioned, involving composition, disjunction and conjunction of causes. We also consider the problems involved in supposing that the appearance of events in time follows an exponential distribution, which are a consequence of the fact that a composition of causes does not follow an exponential distribution, but a “hypoexponential” one. We suggest that a gamma distribution function might more adequately represent the appearance of advances. (shrink)

Working in the weakening of constructive Zermelo-Fraenkel set theory in which the subset collection scheme is omitted, we show that the binary refinement principle implies all the instances of the exponentiation axiom in which the basis is a discrete set. In particular binary refinement implies that the class of detachable subsets of a set form a set. Binary refinement was originally extracted from the fullness axiom, an equivalent of subset collection, as a principle that was sufficient to prove that the (...) Dedekind reals form a set. Here we show that the Cauchy reals also form a set. More generally, binary refinement ensures that one remains in the realm of sets when one starts from discrete sets and one applies the operations of exponentiation and binary product a finite number of times. (shrink)

We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relationsR,S, a componentwise reducibility is defined byR≤S⇔ ∃f∀x, y[x R y↔fS f].Here,fis taken from a suitable class of effective functions. For us the relations will be on natural numbers, andfmust be computable. We show that there is a${\rm{\Pi }}_1^0$-complete equivalence relation, but no${\rm{\Pi }}_k^0$-complete fork≥ 2. We show that${\rm{\Sigma }}_k^0$preorders arising naturally in the above-mentioned areas are${\rm{\Sigma }}_k^0$-complete. This includes polynomial timem-reducibility on (...) exponential time sets, which is${\rm{\Sigma }}_2^0$, almost inclusion on r.e. sets, which is${\rm{\Sigma }}_3^0$, and Turing reducibility on r.e. sets, which is${\rm{\Sigma }}_4^0$. (shrink)

The nature of quantum computation is discussed. It is argued that, in terms of the amount of information manipulated in a given time, quantum and classical computation are equally efficient. Quantum superposition does not permit quantum computers to ''perform many computations simultaneously'' except in a highly qualified and to some extent misleading sense. Quantum computation is therefore not well described by interpretations of quantum mechanics which invoke the concept of vast numbers of parallel universes. Rather, entanglement makes available types (...) of computation processes which, while not exponentially larger than classical ones, are unavailable to classical systems. The essence of quantum computation is that it uses entanglement to generate and manipulate a physical representation of the correlations between logical entities, without the need to completely represent the logical entities themselves. (shrink)

In many real-life situations, we are interested in the value of a physical quantity y that is difficult or impossible to measure directly. To estimate y, we find some easier-to-measure quantities x1, … , xn which are related to y by a known relation y = f. Measurements are never 100% accurate; hence, the measured values equation image are different from xi, and the resulting estimate equation image is different from the desired value y = f. How different can it (...) be? Traditional engineering approach to error estimation in data processing assumes that we know the probabilities of different measurement errors equation image. In many practical situations, we only know the upper bound Δi for this error; hence, after the measurement, the only information that we have about xi is that it belongs to the interval equation image. In this case, it is important to find the range y of all possible values of y = f when xi ∈ xi. We start the paper with a brief overview of the computational complexity of the corresponding interval computation problems: Most of the related problems turn out to be, in general, at least NP-hard. In this paper, we show how the use of quantum computing can speed up some computations related to interval and probabilistic uncertainty. We end the paper with speculations on whether “hypothetic” physical devices can compute NP-hard problems faster than in exponential time. Most of the paper's results were first presented at NAFIPS'2003 [30]. (shrink)

Earlier, we have studied computations possible by physical systems and by algorithms combined with physical systems. In particular, we have analysed the idea of using an experiment as an oracle to an abstract computational device, such as the Turing machine. The theory of composite machines of this kind can be used to understand (a) a Turing machine receiving extra computational power from a physical process, or (b) an experimenter modelled as a Turing machine performing a test of a known (...) physical theory T. Our earlier work was based upon experiments in Newtonian mechanics. Here we extend the scope of the theory of experimental oracles beyond Newtonian mechanics to electrical theory. First, we specify an experiment that measures resistance using a Wheatstone bridge and start to classify the computational power of this experimental oracle using non-uniform complexity classes. Secondly, we show that modelling an experimenter and experimental procedure algorithmically imposes a limit on our ability to measure resistance by the Wheatstone bridge. The connection between the algorithm and physical test is mediated by a protocol controlling each query, especially the physical time taken by the experimenter. In our studies we find that physical experiments have an exponential time protocol, this we formulate as a general conjecture. Our theory proposes that measurability in Physics is subject to laws which are co-lateral effects of the limits of computability and computational complexity. (shrink)

Modal dependence logic was introduced recently by Väänänen. It enhances the basic modal language by an operator = (). For propositional variables p 1, . . . , p n , = (p 1, . . . , p n-1, p n ) intuitively states that the value of p n is determined by those of p 1, . . . , p n-1. Sevenster (J. Logic and Computation, 2009) showed that satisfiability for modal dependence logic is complete for nondeterministic (...) exponential time.In this paper we consider fragments of modal dependence logic obtained by restricting the set of allowed propositional connectives. We show that satisfiability for poor man’s dependence logic, the language consisting of formulas built from literals and dependence atoms using ${\wedge, \square, \lozenge}$ (i. e., disallowing disjunction), remains NEXPTIME-complete. If we only allow monotone formulas (without negation, but with disjunction), the complexity drops to PSPACE-completeness.We also extend Väänänen’s language by allowing classical disjunction besides dependence disjunction and show that the satisfiability problem remains NEXPTIME-complete. If we then disallow both negation and dependence disjunction, satisfiability is complete for the second level of the polynomial hierarchy. Additionally we consider the restriction of modal dependence logic where the length of each single dependence atom is bounded by a number that is fixed for the whole logic. We show that the satisfiability problem for this bounded arity dependence logic is PSPACE-complete and that the complexity drops to the third level of the polynomial hierarchy if we then disallow disjunction.In this way we completely classify the computational complexity of the satisfiability problem for all restrictions of propositional and dependence operators considered by Väänänen and Sevenster. (shrink)

We give resource bounded versions of the Completeness Theorem for propositional and predicate logic. For example, it is well known that every computable consistent propositional theory has a computable complete consistent extension. We show that, when length is measured relative to the binary representation of natural numbers and formulas, every polynomial time decidable propositional theory has an exponential time (EXPTIME) complete consistent extension whereas there is a nondeterministic polynomial time (NP) decidable theory which has no polynomial time complete consistent extension (...) when length is measured relative to the binary representation of natural numbers and formulas. It is well known that a propositional theory is axiomatizable (respectively decidable) if and only if it may be represented as the set of infinite paths through a computable tree (respectively a computable tree with no dead ends). We show that any polynomial time decidable theory may be represented as the set of paths through a polynomial time decidable tree. On the other hand, the statement that every polynomial time decidable, relative to the tally representation of natural numbers and formulas, is equivalent to P = NP. For predicate logic, we develop a complexity theoretic version of the Henkin construction to prove a complexity theoretic version of the Completeness Theorem. Our results imply that that any polynomial space decidable theory △ possesses a polynomial space computable model which is exponential space decidable and thus △ has an exponential space complete consistent extension. Similar results are obtained for other notions of complexity. (shrink)

We present some new decision and comparison problems of unusually high computational complexity. Most of the problems are strictly combinatorial in nature; others involve basic logical notions. Their complexities range from iterated exponential time completeness to (0 time completeness to ((((,0) time completeness to ((((,,0) time completeness. These three ordinals are well known ordinals from proof theory, and their associated com- plexity classes represent new levels of computational complexity for natural decision problems. Proofs will appear in an extended version of (...) this manuscript to be published elsewhere. (shrink)

Guarded fragments of first-order logic were recently introduced by Andreka, van Benthem and Nemeti; they consist of relational first-order formulae whose quantifiers are appropriately relativized by atoms. These fragments are interesting because they extend in a natural way many propositional modal logics, because they have useful model-theoretic properties and especially because they are decidable classes that avoid the usual syntactic restrictions (on the arity of relation symbols, the quantifier pattern or the number of variables) of almost all other known decidable (...) fragments of first-order logic. Here, we investigate the computational complexity of these fragments. We prove that the satisfiability problems for the guarded fragment (GF) and the loosely guarded fragment (LGF) of first-order logic are complete for deterministic double exponential time. For the subfragments that have only a bounded number of variables or only relation symbols of bounded arity, satisfiability is EXPTIME-complete. We further establish a tree model property for both the guarded fragment and the loosely guarded fragment, and give a proof of the finite model property of the guarded fragment. It is also shown that some natural, modest extensions of the guarded fragments are undecidable. (shrink)

Bayesian models are often criticized for postulating computations that are computationally intractable (e.g., NP-hard) and therefore implausibly performed by our resource-bounded minds/brains. Our letter is motivated by the observation that Bayesian modelers have been claiming that they can counter this charge of “intractability” by proposing that Bayesian computations can be tractably approximated. We would like to make the cognitive science community aware of the problematic nature of such claims. We cite mathematical proofs from the computer science literature that (...) show intractable Bayesian computations, such as postulated in existing Bayesian models, cannot be tractably approximated. This does not mean that human brains do not (or cannot) implement the type of algorithms that Bayesian modelers are advancing, but it does mean that proposing that they do by itself does nothing to parry the charge of intractability, because the postulated algorithms are as intractable (i.e., require exponential time) as the computations they try to approximate. Besides our negative message for the community, our letter also makes a positive contribution by referring to a methodology that Bayesian modelers can use to try and parry the charge of intractability in a mathematically sound way. (shrink)

The satisfiability problem for the two-variable fragment of first-order logic is investigated over finite and infinite linearly ordered, respectively wellordered domains, as well as over finite and infinite domains in which one or several designated binary predicates are interpreted as arbitrary wellfounded relations. It is shown that FO 2 over ordered, respectively wellordered, domains or in the presence of one well-founded relation, is decidable for satisfiability as well as for finite satisfiability. Actually the complexity of these decision problems is essentially (...) the same as for plain unconstrained FO 2 , namely non-deterministic exponential time. In contrast FO 2 becomes undecidable for satisfiability and for finite satisfiability, if a sufficiently large number of predicates are required to be interpreted as orderings, wellorderings, or as arbitrary wellfounded relations. This undecidability result also entails the undecidability of the natural common extension of FO 2 and computation tree logic CTL. (shrink)

The notion of (deterministic) chaos is frequently used in an increasing number of scientific (as well as non-scientific) contexts, ranging from mathematics and the physics of dynamical systems to all sorts of complicated time evolutions, e.g., in chemistry, biology, physiology, economy, sociology, and even psychology. Despite (or just because of) these widespread applications, however, there seem to fluctuate around several misunderstandings about the actual impact of deterministic chaos on several problems of philosophical interest, e.g., on matters of prediction and computability, (...) and determinism and the free will. In order to clarify these points a survey of the meaning variance of the concept(s) of deterministic chaos, or the various contexts in which it is applied, is given, and its actual epistemological implications are extracted. In summary, it turns out that the various concepts of deterministic chaos do not constitute a “new science”, or a “revolutionary” change of the “scientific world picture”. Instead, chaos research provides a sort of toolbox of methods which are certainly useful for a more detailed analysis and understanding of such dynamical systems which are, roughly speaking, endowed with the property of exponential sensitivity on initial conditions. Such a property, then, implies merely one, but quantitatively strong type of limitation of long-time computability and predictability, respectively. (shrink)

We investigate the question of whether one can characterize complexity classes in terms of efficient reducibility to the set of Kolmogorov-random strings . This question arises because and , and no larger complexity classes are known to be reducible to in this way. We show that this question cannot be posed without explicitly dealing with issues raised by the choice of universal machine in the definition of Kolmogorov complexity. What follows is a list of some of our main results.• Although (...) Kummer showed that, for every universal machine U there is a time bound t such that the halting problem is disjunctive truth-table reducible to in time t, there is no such time bound t that suffices for every universal machine U. We also show that, for some machines U, the disjunctive reduction can be computed in as little as doubly-exponential time.• Although for every universal machine U, there are very complex sets that are -reducible to , it is nonetheless true that . • Any decidable set that is polynomial-time monotone-truth-table reducible to is in .• Any decidable set that is polynomial-time truth-table reducible to via a reduction that asks at most f queries on inputs of size n lies in. (shrink)

Two-player, zero-sum, non-cooperative, blindfold games in extensive form with incomplete information are considered in this paper. Any information about past moves which players played is stored in a database, and each player can access the database. A polynomial game is a game in which, at each step, all players withdraw at most a polynomial amount of previous information from the database. We show resource-bounded determinacy of some kinds of finite, zero-sum, polynomial games whose pay-off sets are computable by non-deterministic polynomial-time (...) function-oracle Turing machines. We call a pay-off set -determined if, for any polynomial game G associated with the given pay-off set, either player has a winning strategy which is in for any subgames of G. We show that there exists an FP-strongly-determined pay-off set which is computed by an exponential-time oracle Turing machine, where FP is the set of polynomial-time computable functions. We also discuss several relationships between the determinacy of polynomial games and recursion-theoretic properties for the classes co-NP and co-NEXP. We show that the polynomial version of the axiom of choice holds under some assumption of polynomial determinacy for a pay-off set which is polynomial-time computable with parallel queries. This principle of choice implies that co-NP has the separation property. (shrink)

Leonid Levin showed that every algorithm computing a function has an optimal inverter. Recently, we applied his result in various contexts: existence of optimal acceptors, existence of hard sequences for algorithms and proof systems, proofs of Gödel’s incompleteness theorems, analysis of the complexity of the clique problem assuming the nonuniform Exponential Time Hypothesis. We present all these applications here. Even though a simple diagonalization yields Levin’s result, we believe that it is worthwhile to be aware of the explicit result. The (...) purpose of this survey is to convince the reader of our view. (shrink)

We propose two admissible closures $${\mathbb{A}({\sf PTCA})}$$ and $${\mathbb{A}({\sf PHCA})}$$ of Ferreira’s system PTCA of polynomial time computable arithmetic and of full bounded arithmetic (or polynomial hierarchy computable arithmetic) PHCA. The main results obtained are: (i) $${\mathbb{A}({\sf PTCA})}$$ is conservative over PTCA with respect to $${\forall\exists\Sigma^b_1}$$ sentences, and (ii) $${\mathbb{A}({\sf PHCA})}$$ is conservative over full bounded arithmetic PHCA for $${\forall\exists\Sigma^b_{\infty}}$$ sentences. This yields that (i) the $${\Sigma^b_1}$$ definable functions of $${\mathbb{A}({\sf PTCA})}$$ are the polytime functions, and (ii) the $${\Sigma^b_{\infty}}$$ definable (...) functions of $${\mathbb{A}({\sf PHCA})}$$ are the functions in the polynomial time hierarchy. (shrink)

Between Calculability and Non-Calculability. Issues of Calculability and Predictability in the Physics of Complex Systems. The ability to predict has been a very important qualifier of what constitutes scientific knowledge, ever since the successes of Babylonian and Greek astronomy. More recent is the general appreciation of the fact that in the presence of deterministic chaos, predictability is severely limited (the so-called ‘butterfly effect’): Nearby trajectories diverge during time evolution; small errors typically grow exponentially with time. The system obeys deterministic laws (...) and still is unpredictable, seemingly a paradox for the traditional viewpoint of Laplacian determinisms. With the concept of deterministic chaos the epistemological issue about an adequate understanding of predictability is no longer just a mere philosophical topic. Physicists on the one hand recognize the limits of (long term) predictability, computability and even of scientific knowledge, on the other hand they work on concepts for extending the horizon of predictability. It is shown in this paper that physics of complex systems is useful to clarify the jungle of different meanings of the terms ‘predictability’ and ‘computability’ — also with philosophical implications for understanding science and nature. Today, from the physical point of view, the relevance of the concepts of predictability seems to be underestimated by philosophers as a mere methodological topic. In the paper I analyse the importance of predictability and computability in physics of complex systems. I show a way how to cope with problems of unpredictability and noncomputability. Nine different concepts of predictability and computability (i.e. open solution, sensitivity/chaos, redundancy/chance) are presented, compared and evaluated. (shrink)

We identify the computational complexity of the satisfiability problem for FO 2 , the fragment of first-order logic consisting of all relational first-order sentences with at most two distinct variables. Although this fragment was shown to be decidable a long time ago, the computational complexity of its decision problem has not been pinpointed so far. In 1975 Mortimer proved that FO 2 has the finite-model property, which means that if an FO 2 -sentence is satisfiable, then it has a finite (...) model. Moreover, Mortimer showed that every satisfiable FO 2 -sentence has a model whose size is at most doubly exponential in the size of the sentence. In this paper, we improve Mortimer's bound by one exponential and show that every satisfiable FO 2 -sentence has a model whose size is at most exponential in the size of the sentence. As a consequence, we establish that the satisfiability problem for FO 2 is NEXPTIME-complete. (shrink)

In first order logic without equality, but with arbitrary relations and functions the ∃*∀∃* class is the unique maximal solvable prefix class. We show that the satisfiability problem for this class is decidable in deterministic exponential time The result is established by a structural analysis of a particular infinite subset of the Herbrand universe and by a polynomial space bounded alternating procedure.

This paper is motivated by the question whether there exists a logic capturing polynomial time computation over unordered structures. We consider several algorithmic problems near the border of the known, logically defined complexity classes contained in polynomial time. We show that fixpoint logic plus counting is stronger than might be expected, in that it can express the existence of a complete matching in a bipartite graph. We revisit the known examples that separate polynomial time from fixpoint plus counting. We show (...) that the examples in a paper of Cai, Fürer, and Immerman, when suitably padded, are in choiceless polynomial time yet not in fixpoint plus counting. Without padding, they remain in polynomial time but appear not to be in choiceless polynomial time plus counting. Similar results hold for the multipede examples of Gurevich and Shelah, except that their final version of multipedes is, in a sense, already suitably padded. Finally, we describe another possible candidate, involving determinants, for the task of separating polynomial time from choiceless polynomial time plus counting. (shrink)

We study a refined framework of parameterized complexity theory where the parameter dependence of fixed-parameter tractable algorithms is not arbitrary, but restricted by a function in some family . For every family of functions, this yields a notion of -fixed-parameter tractability. If is the class of all polynomially bounded functions, then -fixed-parameter tractability coincides with polynomial time decidability and if is the class of all computable functions, -fixed-parameter tractability coincides with the standard notion of fixed-parameter tractability. There are interesting choices (...) of between these two extremes, for example the class of all singly exponential functions. In this article, we study the general theory of -fixed-parameter tractability. We introduce a generic notion of reduction and two classes -W[P] and -XP, which may be viewed as analogues of NP and EXPTIME, respectively, in the world of -fixed-parameter tractability. (shrink)

In recent times, the exponential growth of sequenced genomes and structural knowledge of proteins, as well as the development of computational tools and controlled vocabularies to deal with this growth, has fueled a demand for conceptual clarification regarding the concept of function in molecular biology. In this article, we will attempt to develop an account of function fit to deal with the conceptual/philosophical problems in that domain, but which can be extended to other areas of biology. To provide this account, (...) we will argue for three theses: (1) some authors have confused metatheoretical issues (about the meaning and application criteria of terms) with metaphysical ones (about teleology); this led them to (2) look for explicit definitions of “function”, in terms of necessary and sufficient criteria of application, in order to make the concept of function eliminable; however, (3) if one leaves metaphysical worries aside and focuses on functional attribution practices, it is more adequate to say that the concept of function has an open texture. That is, that a multiplicity of application criteria is available, none of which is sufficient nor necessary to attribute a function to a trait, and which only in concert form a clear picture. We distinguish this thesis from some usual forms of pluralism. Finally, we will illustrate this account with a historical reconstruction of the ascription of a water transport function to aquaporins. (shrink)

According to Craig Callender [2022], the ‘received view’ across the social sciences is that, when it comes to time and preference, only exponential time discounting is rational. Callender argues that this view is false, even pernicious. Here I endorse what I take to be Callender’s main argument, but only in so far as the received view is understood in a particular way. I go on to propose a different way of understanding the received view that makes it true. In short: (...) When time discounting is suitably conceived, the exponential form of the discounting function is indeed uniquely rational. (shrink)

Cost-based abduction, which is a technique for identifying the best explanation for a given observation based on the assumption of a set of hypothesis, is a useful knowledge processing framework for practical problems such as diagnosis, design and planning. However, the speed of reasoning of this approach is often slow. To overcome this problem, Kato et al. previously presented a more efficient cost-based abduction system, that utilized the A * search technique, however, the time and space complexities in this technique (...) are exponential, so the identification of the optimal solution is difficult in practical applications. In this paper, we present three new systems in which the user can define the computational complexity, for identification of a near-optimal solution. First, we introduce two search control techniques; a real-time A * search approach in which the user can define the look-ahead depth or space, and the multi-agent real-time A * approach in which the user can define the number of real-time A * agents used in the search. We describe the implementation of three cost-based abduction reasoning systems for predicate logic knowledge bases and test the proposed systems using a diagnostic logic circuit problem. The results show that proposed systems can identify a near-optimal solution according to the predefined polynomial order of complexity, including the selection of either linear or exponential computational complexity. It is also shown that inference time and success rate are dependent on the user-defined parameters, that the three proposed systems exhibit similar performance characteristics, and that they all offer significant speed advantages over the previously described technique. (shrink)

Do hard law international organizations use jurisprudence differently than soft law ones? Precedent can be asset or an encumbrance to international organizations and their members, depending on their aims and on the policy area. Linking current decisions to previously-agreed ones helps to increase cohesion, facilitate consensus among members, and borrow authority – benefits that might be more necessary for some organizations than for others. To compare whether the features of norm-producing organizations correlate with their preference for jurisprudence, we compare two (...) organs from the United Nations system: the Security Council, which produces binding decisions, and the General Assembly, which delivers soft law resolutions. We explore the citation networks formed by the approximately 20,400 resolutions adopted by each organ between 1946 and 2019 to test their differences with regards to the dynamics of citation formation, concentration of citations, and timing. Descriptive results reveal the main periods of jurisprudential activity by the Security Council and the General Assembly, but find no sizeable difference in their overall rate of precedent usage. We apply the Citation Exponential Random Graph Model (cERGM) to test for network determinants of citations and find additional similarities on transitivity and homophily, but also variations regarding preferential attachment. (shrink)

We investigate the polynomial time isomorphic type structure of (the class of tally, polynomial time computable sets). We partition P T into six parts: D −, D^ − , C, S, F, F^, and study their p-isomorphic properties separately. The structures of , , and are obvious, where F, F^, and C are the class of tally finite sets, the class of tally co-finite sets, and the class of tally bi-dense sets respectively. The following results for the structures of and (...) will be proved, where D^ is the class of tally, co-dense, polynomial time computable sets and S is the class of tally, scatted (i.e., neither dense nor co-dense), polynomial time computable sets. 1. is a countable distributive lattice with the greatest element. 2. Infinitely many intervals in can be distinguished by first order formulas. 3. There exist infinitely many nontrivial automorphisms for . 4. is not distributive, but any interval in is a countable distributive lattice. RID=""ID="" Mathematics Subject Classification (2000): 03D15, 03D25, 03D30, 03D35, 06A06, 06B20 RID=""ID="" Key words or phrases: Computational complexity – Polynomial time – Degree structure – Lattice – Isomorphism RID=""ID="" Part of this work was done when the author was a PhD student at the University of Heidelberg under the direction of Professor Ambos-Spies. (shrink)

In the past four decades, the notion of quantum polynomial-time computability has been mathematically modeled by quantum Turing machines as well as quantum circuits. This paper seeks the third model, which is a quantum analogue of the schematic definition of recursive functions. For quantum functions mapping finite-dimensional Hilbert spaces to themselves, we present such a schematic definition, composed of a small set of initial quantum functions and a few construction rules that dictate how to build a new quantum function from (...) the existing ones. We prove that our schematic definition precisely characterizes all functions that can be computable with high success probabilities on well-formed quantum Turing machines in polynomial time, or equivalently uniform families of polynomial-size quantum circuits. Our new, schematic definition is quite simple and intuitive and, more importantly, it avoids the cumbersome introduction of the well-formedness condition imposed on a quantum Turing machine model as well as of the uniformity condition necessary for a quantum circuit model. Our new approach can further open a door to the descriptional complexity of quantum functions, to the theory of higher-type quantum functionals, to the development of new first-order theories for quantum computing, and to the designing of programming languages for real-life quantum computer. (shrink)

In the dissertation we study the complexity of generalized quantifiers in natural language. Our perspective is interdisciplinary: we combine philosophical insights with theoretical computer science, experimental cognitive science and linguistic theories. -/- In Chapter 1 we argue for identifying a part of meaning, the so-called referential meaning (model-checking), with algorithms. Moreover, we discuss the influence of computational complexity theory on cognitive tasks. We give some arguments to treat as cognitively tractable only those problems which can be computed in polynomial time. (...) Additionally, we suggest that plausible semantic theories of the everyday fragment of natural language can be formulated in the existential fragment of second-order logic. -/- In Chapter 2 we give an overview of the basic notions of generalized quantifier theory, computability theory, and descriptive complexity theory. -/- In Chapter 3 we prove that PTIME quantifiers are closed under iteration, cumulation and resumption. Next, we discuss the NP-completeness of branching quantifiers. Finally, we show that some Ramsey quantifiers define NP-complete classes of finite models while others stay in PTIME. We also give a sufficient condition for a Ramsey quantifier to be computable in polynomial time. -/- In Chapter 4 we investigate the computational complexity of polyadic lifts expressing various readings of reciprocal sentences with quantified antecedents. We show a dichotomy between these readings: the strong reciprocal reading can create NP-complete constructions, while the weak and the intermediate reciprocal readings do not. Additionally, we argue that this difference should be acknowledged in the Strong Meaning hypothesis. -/- In Chapter 5 we study the definability and complexity of the type-shifting approach to collective quantification in natural language. We show that under reasonable complexity assumptions it is not general enough to cover the semantics of all collective quantifiers in natural language. The type-shifting approach cannot lead outside second-order logic and arguably some collective quantifiers are not expressible in second-order logic. As a result, we argue that algebraic (many-sorted) formalisms dealing with collectivity are more plausible than the type-shifting approach. Moreover, we suggest that some collective quantifiers might not be realized in everyday language due to their high computational complexity. Additionally, we introduce the so-called second-order generalized quantifiers to the study of collective semantics. -/- In Chapter 6 we study the statement known as Hintikka's thesis: that the semantics of sentences like ``Most boys and most girls hate each other'' is not expressible by linear formulae and one needs to use branching quantification. We discuss possible readings of such sentences and come to the conclusion that they are expressible by linear formulae, as opposed to what Hintikka states. Next, we propose empirical evidence confirming our theoretical predictions that these sentences are sometimes interpreted by people as having the conjunctional reading. -/- In Chapter 7 we discuss a computational semantics for monadic quantifiers in natural language. We recall that it can be expressed in terms of finite-state and push-down automata. Then we present and criticize the neurological research building on this model. The discussion leads to a new experimental set-up which provides empirical evidence confirming the complexity predictions of the computational model. We show that the differences in reaction time needed for comprehension of sentences with monadic quantifiers are consistent with the complexity differences predicted by the model. -/- In Chapter 8 we discuss some general open questions and possible directions for future research, e.g., using different measures of complexity, involving game-theory and so on. -/- In general, our research explores, from different perspectives, the advantages of identifying meaning with algorithms and applying computational complexity analysis to semantic issues. It shows the fruitfulness of such an abstract computational approach for linguistics and cognitive science. (shrink)

The proposed changes to the Common Rule, described in the recent Advanced Notice of Proposed Rulemaking, come more than 20 years after the U.S. Department of Health and Human Services adopted the Rule in 1991. Since that time, human subjects research has changed in significant ways. Not only has the volume of clinical research grown dramatically, this research is now regularly conducted at multiple collaborative sites that are often outside of the United States. Research takes place not only in academic (...) medical centers, but also at outpatient clinics, community hospitals, and other nontraditional venues. In addition, technological advances, such as sophisticated computer software programs, the Internet, social media, new research methods, and mobile applications have exponentially increased the volume of data available and the possibilities for accessing, analyzing, and sharing that data. (shrink)

My title refers to a very modern problem, for what else is modernization than a process of rational differentiation of society in autonomous, mutually isolated sub-spheres, to the point where no one any longer knows what the unity of it all is? We differentiate, we specialize, we hyperspecialize, and then we get puzzled over the fragmentation we have produced around us, between ourselves and even within ourselves. Look at our own area. You cannot even specialize in practical ethics any more. (...) You have to limit your attention to medical ethics, for example, the ethics of engineering, or business ethics. And within business ethics, my own field of research, the homo universalis is also threatened with extinction. You can do marketing ethics, ethics of finance or computer ethics, until you finally become the typical ‘expert’: someone who knows almost everything about almost nothing.From the despair over hyper-differentiation, the call for integration arises: the call for meaning, for reconfiguration, for making sense of our world and our lives again, the call for reconnection with the great traditions of our culture, the call for community.If we read the great theorists of modernization — Weber, Durkheim, Parsons, Habermas, Münch — we learn that the quest for integration is in fact an equally important aspect of modernization as is differentiation. They are two sides of the same coin. In this sense, I think, the integrative endeavour of the EEN can still be considered a modern one.We are presently facing an escalation, or a climax, of modernity. We live in a state of hypermodernity, in which technological, economic and cultural forces dynamize our society on an unprecedented scale. We are really living high up on the dazzling slopes of the exponential growth curves that the Club of Rome predicted over 25 years ago. Everyone speaks of change. Everything is changing, and with institutionalized change, everything has become uncertain. Within uncertainty, however, social disintegration is lurking. Does not the structural uncertainty that we are introducing in our society bring us back to a state of nature, to a state outside the hypothetical social contract on which modern social communities are based? Is not the life of the individualized, flexible wanderers on the labour market again resembling the pledge of man which Hobbes described as ‘solitary, nasty and brutish’ . Has not the life of many in our society again become ‘very unsafe and very insecure, full of fears and continual dangers’, in the way that Locke depicted the state of nature .I understand business ethics as an integrative undertaking in our society, integrative in particular with respect to the economy and the realm of formal organization, integrative also at the interface between life-world and system, to use the terminology of Habermas.Integrative endeavours in our society have an ambiguous relation to change. Change is a key challenge to business ethics. Should we accept disruptive forms of change as inevitable, in order to remain on speaking terms with the economy and its spokesmen? Or should we fiercely resist certain changes? Is change on our side, perhaps? Business ethics is sometimes presented as a way to help managers cope with the many paradoxes of our time. One-dimensional technological rationality, we say, is no longer adequate to grasp the complexities, ambiguities and paradoxes of our world. Successful management requires more flexible, more creative forms of thinking. Philosophy and ethics are then presented as alternatives. But then aren’t we, the philosophers, simply promoting ourselves as the new masters of change for our time? Isn’t the so-called postmodern consciousness in fact an ideological underpinning of hyper differentiation, and in this sense the ultimate self-realization of the spirit of modernity? What sense of direction do we offer, as business ethicists?I would like to speak about the integration of micro, meso and macro-levels in business ethics, from the perspective of social change. My basic thesis is that only an adequate ethics of responsibility can integrate a highly differentiated and ultra-complex society like ours. This integration through responsibility opens up new directions of social change, that proceed simultaneously at the micro, meso and macro-level.In order not to complicate matters too much, I will limit myself to two dimensions of change which are important for business ethics at the moment: economic change ; organizational change . In relation to these changes, I will conclude with some reflections on changes in business ethics itself, the ones that I think are needed. (shrink)

Time plays a significant role in science and everyday life. Despite being experienced as a continuous flow, computational models of consciousness are typically restricted to a sequential temporal structure. This difference poses a serious challenge for computational phenomenology—a novel field combining phenomenology and computational modelling. By analysing the temporal structure of the active inference framework, we show that an integrated continuity of time can be achieved by merging Husserlian temporality with a sequential order of time. We also show that a (...) Markov blanket of the present moment integrates past and future moments of both subjective temporality and objective time in an asynchronous manner. By applying the integrated continuity, it is clear that active inference makes use of both subjective temporality and objective time in an integrated fashion. We conclude that active inference, on a temporal note, qualifies as a computational model for phenomenological investigations. (shrink)

The problem of how mathematics and physics are related at a foundational level is of interest. The approach taken here is to work towards a coherent theory of physics and mathematics together by examining the theory experiment connection. The role of an implied theory hierarchy and use of computers in comparing theory and experiment is described. The main idea of the paper is to tighten the theory experiment connection by bringing physical theories, as mathematical structures over C, the complex numbers, (...) closer to what is actually done in experimental measurements and computations. The method replaces C by C n which is the set of pairs, R n,I n, of n figure rational numbers in some basis. The properties of these numbers are based on those of numerical measurement outcomes for continuous variables. A model of space and time based on R n is discussed. The model is scale invariant with regions of constant step size interrupted by exponential jumps. A method of taking the limit n→∞ to obtain locally flat continuum-based space and time is outlined. Also R n based space is invariant under scale transformations. These correspond to expansion and contraction of space relative to a flat background. The location of the origin, which is a space and time singularity, does not change under these transformations. Some properties of quantum mechanics, based on C n and on R n space are briefly investigated. (shrink)

The rapid pace of development over the last few decades in the domain of machine learning mirrors the advances made in the field of quantum computing. It is natural to ask whether the conventional machine learning algorithms could be optimized using the present-day noisy intermediate-scale quantum technology. There are certain computational limitations while training a machine learning model on a classical computer. Using quantum computation, it is possible to surpass these limitations and carry out such calculations in an optimized manner. (...) This study illustrates the working of the quantum support vector machine classification model which guarantees an exponential speed-up over its typical alternatives. This research uses the quantum SVM model to solve the classification task of a malignant breast cancer diagnosis. This study also demonstrates a comparative analysis of distinct forms of SVM algorithms concerning their time complexity and performances on standard evaluation metrics, namely accuracy, precision, recall, and F1-score, to exemplify the supremacy of quantum SVM over its conventional variants. (shrink)

Much like admissibility is the key concept underlying preferred semantics, strong admissibility is the key concept underlying grounded semantics, as membership of a strongly admissible set is sufficient to show membership of the grounded extension. As such, strongly admissible sets and labellings can be used as an explanation of membership of the grounded extension, as is for instance done in some of the proof procedures for grounded semantics. In the current paper, we present two polynomial algorithms for constructing relatively small (...) strongly admissible labellings, with associated min–max numberings, for a particular argument. These labellings can be used as relatively small explanations for the argument’s membership of the grounded extension. Although our algorithms are not guaranteed to yield an absolute minimal strongly admissible labelling for the argument (as doing so would have implied an exponential complexity), our best performing algorithm yields results that are only marginally larger. Moreover, the runtime of this algorithm is an order of magnitude smaller than that of the existing approach for computing an absolute minimal strongly admissible labelling for a particular argument. As such, we believe that our algorithms can be of practical value in situations where the aim is to construct a minimal or near-minimal strongly admissible labelling in a time-efficient way. (shrink)

The scattering number and isolated scattering number of a graph have been introduced in relation to Hamiltonian properties and network vulnerability, and the isolated scattering number plays an important role in characterizing graphs with a fractional 1-factor. Here we investigate the computational complexity of one variant, namely, the weighted isolated scattering number. We give a polynomial time algorithm to compute this parameter of interval graphs, an important subclass of perfect graphs.

The medium‐independence of computational descriptions has shaped common conceptions of computational explanation. So long as our goal is to explain how a system successfully carries out its computations, then we only need to describe the abstract series of operations that achieve the desired input–output mapping, however they may be implemented. It is argued that this abstract conception of computational explanation cannot be applied to so‐called real‐time computing systems, in which meeting temporal deadlines imposed by the systems with which a (...) device interfaces are constitutive of the computing tasks that a device performs. Instead, real‐time computing reveals the need for alternative conceptions of computational explanation, as well as computational implementation, that eschew medium‐independence. (shrink)

In this paper, the stability of switched neural networks with interval parameter uncertainties and time delays is investigated. First, the conditions for the existence and uniqueness of the equilibrium point of the system are discussed. Second, the average dwell time approach and M-matrix property are employed to obtain conditions to ensure the globally exponential stability of the delayed SNNs under constrained switching. Third, by resorting to inequality technique and the idea of vector Lyapunov function, sufficient condition to ensure the robust (...) exponential stability of the delayed SNNs under arbitrary switching is derived. The form of the constructed Lyapunov functions is simple, which has certain commonality in studying delayed SNNs, and the proposed results not only are explicit but also reveal the relationship between the constrained switching and the arbitrary switching of the SNNs. Finally, two numerical examples are presented to illustrate the effectiveness and less conservativeness of the main results compared with the existing literature. (shrink)

The paper aims to highlight similarities between computational routines of mentally traveling the present time, on the one hand, and routines of mentally traveling other times, on the other hand. The first and second sections, in which I lay out an eternalist view of the world and the massive modularity account of the architecture of the human mind, are intended to set the stage. Subsequently, I clarify the idea that we mentally travel the present. This explanation resorts to a cognitive (...) mechanism I have proposed elsewhere. Finally, I submit that a similar computational routine takes place when we travel other times, be they earlier or later than the present moment. Keywords: eternalism, modularity, episodic memory, four-dimensionalism. (shrink)