This paper considers the computational complexity of the disjunction and existential properties of intuitionistic logic. We prove that the disjunction property holds feasibly for intuitionistic propositional logic; i.e., from a proof of A v B, a proof either of A or of B can be found in polynomial time. For intuitionistic predicate logic, we prove superexponential lower bounds for the disjunction property, namely, there is a superexponential lower bound on the time required, given a proof of A v B, to (...) produce one of A and B which is true. In addition, there is superexponential lower bound on the size of terms which fulfill the existential property of intuitionistic predicate logic. There are superexponential upper bounds for these problems, so the lower bounds are essentially optimal. (shrink)

We give a combinatorial analysis (using edge expansion) of a variant of the iterative expander construction due to Reingold, Vadhan, and Wigderson [44], and show that this analysis can be formalized in the bounded arithmetic system VNC^1 (corresponding to the “NC^1 reasoning”). As a corollary, we prove the assumption made by Jeřábek [28] that a construction of certain bipartite expander graphs can be formalized in VNC^1 . This in turn implies that every proof in Gentzen's sequent calculus LK of a (...) monotone sequent can be simulated in the monotone version of LK (MLK) with only polynomial blowup in proof size, strengthening the quasipolynomial simulation result of Atserias, Galesi, and Pudlák [9]. (shrink)

We give a uniform proof of the theorems of Yao and Beigel–Tarui representing ACC predicates as constant depth circuits with MODm\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hbox {MOD}_{m}$$\end{document} gates and a symmetric gate. The proof is based on a relativized, generalized form of Toda’s theorem expressed in terms of closure properties of formulas under bounded universal, existential and modular counting quantifiers. This allows the main proofs to be expressed in terms of formula classes instead of Boolean circuits. (...) The uniform version of the Beigel–Tarui theorem is then obtained automatically via the Furst–Saxe–Sipser and Paris–Wilkie translations. As a special case, we obtain a uniform version of Razborov and Smolensky’s representation of AC0[p]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hbox {AC}^{0}[p]$$\end{document} circuits. The paper is partly expository, but is also motivated by the desire to recast Toda’s theorem, the Beigel–Tarui theorem, and their proofs into the language of bounded arithmetic. However, no knowledge of bounded arithmetic is needed. (shrink)

We give the first systematic study of strong isomorphism reductions, a notion of reduction more appropriate than polynomial time reduction when, for example, comparing the computational complexity of the isomorphim problem for different classes of structures. We show that the partial ordering of its degrees is quite rich. We analyze its relationship to a further type of reduction between classes of structures based on purely comparing for every n the number of nonisomorphic structures of cardinality at most n in both (...) classes. Furthermore, in a more general setting we address the question of the existence of a maximal element in the partial ordering of the degrees. (shrink)

We introduce martingales defined by probabilistic strategies, in which randomness is used to decide whether to bet. We show that different criteria for the success of computable probabilistic strategies can be used to characterize ML-randomness, computable randomness, and partial computable randomness. Our characterization of ML-randomness partially addresses a critique of Schnorr by formulating ML randomness in terms of a computable process rather than a computably enumerable function.

We consider tautologies expressing equivalence‐chain properties in the spirit of Thapen and Krajíček, which are candidates for exponentially separating depth k and depth Frege proof systems. We formulate a special case where the initial member of the equivalence chain is fully specified and the equivalence‐chain implications are actually equivalences. This special case is shown to lead to polynomial size resolution refutations. Thus it cannot be used for separating depth k and depth propositional systems. We state some Håstad switching lemma conditions (...) that restrict the possible propositional proofs in more general situations. (shrink)

We prove that the problem of determining the minimum propositional proof length is NP- hard to approximate within a factor of 2 log 1 - o(1) n . These results are very robust in that they hold for almost all natural proof systems, including: Frege systems, extended Frege systems, resolution, Horn resolution, the polynomial calculus, the sequent calculus, the cut-free sequent calculus, as well as the polynomial calculus. Our hardness of approximation results usually apply to proof length measured either by (...) number of symbols or by number of inferences, for tree-like or dag-like proofs. We introduce the Monotone Minimum (Circuit) Satisfying Assignment problem and reduce it to the problems of approximation of the length of proofs. (shrink)

This paper studies the complexity of constant depth propositional proofs in the cedent and sequent calculus. We discuss the relationships between the size of tree-like proofs, the size of dag-like proofs, and the heights of proofs. The main result is to correct a proof construction in an earlier paper about transformations from proofs with polylogarithmic height and constantly many formulas per cedent.

We extend results of Bonet, Buss and Pitassi on Bondy’s Theorem and of Nozaki, Arai and Arai on Bollobás’ Theorem by proving that Frankl’s Theorem on the trace of sets has quasipolynomial size Frege proofs. For constant values of the parametert, we prove that Frankl’s Theorem has polynomial size AC0-Frege proofs from instances of the pigeonhole principle.

In order to be a self-governing agent, a person must govern the process by means of which she acquires the intention to act as she does. But what does governing this process require? The standard compatibilist answers to this question all assume that autonomous actions differ from nonautonomous actions insofar as they are a more perfect expression of the agent’s agency. I challenge this conception of autonomous agents as super agents. The distinguishing feature of autonomous agents is, I argue, the (...) nonagential role they play in the formation of their intentions. I offer an account of the relevant role. (shrink)

Formal models of appearance and reality have proved fruitful for investigating structural properties of perceptual knowledge. This paper applies the same approach to epistemic justification. Our central goal is to give a simple account of The Preface, in which justified belief fails to agglomerate. Following recent work by a number of authors, we understand knowledge in terms of normality. An agent knows p iff p is true throughout all relevant normal worlds. To model The Preface, we appeal to the normality (...) of error. Sometimes, it is more normal for reality and appearance to diverge than to match. We show that this simple idea has dramatic consequences for the theory of knowledge and justification. Among other things, we argue that a proper treatment of The Preface requires a departure from the internalist idea that epistemic justification supervenes on the appearances and the widespread idea that one knows most when free from error. (shrink)

Buss, S.R., The undecidability of k-provability, Annals of Pure and Applied Logic 53 75-102. The k-provability problem is, given a first-order formula ø and an integer k, to determine if ø has a proof consisting of k or fewer lines . This paper shows that the k-provability problem for the sequent calculus is undecidable. Indeed, for every r.e. set X there is a formula ø and an integer k such that for all n,ø has a proof of k sequents (...) if and only if n ε X. (shrink)

In this enlightening book, Sam Harris argues that free will is an illusion but that this truth should not undermine morality or diminish the importance of social and political freedom; indeed, this truth can and should change the way we think about some of the most important questions in life.

Inquiry aims at knowledge. Your inquiry into a question succeeds just in case you come to know the answer. However, combined with a common picture on which misleading evidence can lead knowledge to be lost, this view threatens to recommend a novel form of dogmatism. At least in some cases, individuals who know the answer to a question appear required to avoid evidence bearing on it. In this paper, we’ll aim to do two things. First, we’ll present an argument for (...) this novel form of dogmatism and show that it presents a substantive challenge. Second, we’ll consider a way those who take knowledge to be the aim of inquiry can mount a response. In the course of doing so, we’ll try to get clearer on the normative connections between inquiry, knowledge and evidence gathering. (shrink)

Philosophy and Phenomenological Research, Volume 104, Issue 1, Page 19-49, January 2022.

In non‐literal uses of language, the content an utterance communicates differs from its literal truth conditions. Loose talk is one example of non‐literal language use (amongst many others). For example, what a loose utterance of (1) communicates differs from what it literally expresses: (1) Lena arrived at 9 o'clock. Loose talk is interesting (or so I will argue). It has certain distinctive features which raise important questions about the connection between literal and non‐literal language use. This paper aims to (i.) (...) introduce a range of novel data demonstrating certain overlooked features of loose talk, and (ii.) develop a new theory of the phenomenon which accounts for these data. In particular, this theory is motivated by the need to explain minimal pairs such as (2)-(3): (2) Lena arrived at 9 o'clock, but she did not arrive at 9 o'clock exactly. (3) ?? Lena did not arrive at 9 o'clock exactly, but she arrived at 9 o'clock. (2) and (3) agree in their truth conditions. Yet they differ in felicity. As such, they constitute a problem for any account which hopes to predict the acceptability of the loose use of a sentence from its truth conditions and the context of utterance alone. Instead, it will be argued, to explain loose talk phenomena we must posit an additional layer of meaning outstripping truth conditions. This layer of meaning is shown to exhibit a range of properties, all of which point to its being semantically encoded. Thus, if correct, the theory provides a new example of how semantic meaning must extend beyond literal, truth‐conditional content. (shrink)

Predictive processing accounts of neural function view the brain as a kind of prediction machine that forms models of its environment in order to anticipate the upcoming stream of sensory stimulation. These models are then continuously updated in light of incoming error signals. Predictive processing has offered a powerful new perspective on cognition, action, and perception. In this chapter we apply the insights from predictive processing to the study of emotions. The upshot is a picture of emotion as inseparable from (...) perception and cognition, and a key feature of the embodied mind. (shrink)

We develop a new version of the causal theory of spacetime. Whereas traditional versions of the theory seek to identify spatiotemporal relations with causal relations, the version we develop takes causal relations to be the grounds for spatiotemporal relations. Causation is thus distinct from, and more basic than, spacetime. We argue that this non-identity theory, suitably developed, avoids the challenges facing the traditional identity theory.

Standard approaches to counterfactuals in the philosophy of explanation are geared toward causal explanation. We show how to extend the counterfactual theory of explanation to non-causal cases, involving extra-mathematical explanation: the explanation of physical facts by mathematical facts. Using a structural equation framework, we model impossible perturbations to mathematics and the resulting differences made to physical explananda in two important cases of extra-mathematical explanation. We address some objections to our approach.

Suppositional theories of conditionals take apparent similarities between supposition and conditionals as a starting point, appealing to features of the former to provide an account of the latter. This paper develops a novel form of suppositional theory, one which characterizes the relationship at the level of semantics rather than at the level of speech acts. In the course of doing so, it considers a range of novel data which shed additional light on how conditionals and supposition interact.

On a now orthodox view, humans and many other animals possess a “number sense,” or approximate number system, that represents number. Recently, this orthodox view has been subject to numerous critiques that question whether the ANS genuinely represents number. We distinguish three lines of critique – the arguments from congruency, confounds, and imprecision – and show that none succeed. We then provide positive reasons to think that the ANS genuinely represents numbers, and not just non-numerical confounds or exotic substitutes for (...) number, such as “numerosities” or “quanticals,” as critics propose. In so doing, we raise a neglected question: numbers of what kind? Proponents of the orthodox view have been remarkably coy on this issue. But this is unsatisfactory since the predictions of the orthodox view, including the situations in which the ANS is expected to succeed or fail, turn on the kind of number being represented. In response, we propose that the ANS represents not only natural numbers, but also non-natural rational numbers. It does not represent irrational numbers, however, and thereby fails to represent the real numbers more generally. This distances our proposal from existing conjectures, refines our understanding of the ANS, and paves the way for future research. (shrink)

To treat some human beings as less worthy of concern and respect than others is to lose sight of their humanity. But what does this moral blindness amount to? In exploring the value of humanity, the essays in this volume offer a wide range of competing, yet overlapping, answers to this question. Some essays examine influential views in the history of Western philosophy. In others, philosophers currently working in ethics develop and defend their own views. Some essays appeal to distinctively (...) human capacities. Others argue that our obligations to one another are ultimately grounded in self-interest or certain shared interests or our natural sociability. The philosophers featured here disagree about whether the value of human beings depends on the value of anything else. They disagree about how reason and rationality relate to this value, and even about whether we can reason our way to discovering it. This rich selection of proposals encourages us to rethink some of our own deepest assumptions about the moral significance of being human. (shrink)

I give a new argument for the moral difference between lying and misleading. First, following David Lewis, I hold that conventions of truthfulness and trust fix the meanings of our language. These conventions generate fair play obligations. Thus, to fail to conform to the conventions of truthfulness and trust is unfair. Second, I argue that the liar, but not the misleader, fails to conform to truthfulness. So the liar, but not the misleader, does something unfair. This account entails that bald-faced (...) lies are wrong, that we can lie nonlinguistically, and that linguistic innovation is morally significant. (shrink)

In an interesting experimental study, Bonini et al. (1999) present partial support for truth-gap theories of vagueness. We say this despite their claim to find theoretical and empirical reasons to dismiss gap theories and despite the fact that they favor an alternative, epistemic account, which they call ‘vagueness as ignorance’. We present yet more experimental evidence that supports gap theories, and argue for a semantic/pragmatic alternative that unifies the gappy supervaluationary approach together with its glutty relative, the subvaluationary approach.

The curriculum design, faculty characteristics, and experience of implementing masters' level international research ethics training programs supported by the Fogarty International Center was investigated. Multiple pedagogical approaches were employed to adapt to the learning needs of the trainees. While no generally agreed set of core competencies exists for advanced research ethics training, more than 75% of the curricula examined included international issues in research ethics, responsible conduct of research, human rights, philosophical foundations of research ethics, and research regulation and ethical (...) review process. Common skills taught included critical thinking, research methodology and statistics, writing, and presentation proficiency. Curricula also addressed the cultural, social, and religious context of the trainees related to research ethics. Programs surveyed noted trainee interest in Western concepts of research ethics and the value of the transnational exchange of ideas. Similar faculty expertise profiles existed in all programs. Approximately 40% of faculty were female. Collaboration between faculty from low- and middleincome countries (LMICs) and high-income countries (HICs) occurred in most programs and at least 50% of HIC faculty had previous LMIC experience. This paper is part of a collection of papers analyzing the Fogarty International Research Ethics Education and Curriculum Development program. (shrink)

Bestselling author Sam Harris dismantles the most common justification for religious faith-that a moral system cannot be based on science.

This paper refines a controversial proposal: that core systems belong to a perceptual kind, marked out by the format of its representational outputs. Following Susan Carey, this proposal has been understood in terms of core representations having an iconic format, like certain paradigmatically perceptual outputs. I argue that they don’t, but suggest that the proposal may be better formulated in terms of a broader analogue format type. Formulated in this way, the proposal accommodates the existence of genuine icons in perception, (...) and avoids otherwise troubling objections. (shrink)

There is a large literature exploring how accuracy constrains rational degrees of belief. This paper turns to the unexplored question of how accuracy constrains knowledge. We begin by introducing a simple hypothesis: increases in the accuracy of an agent’s evidence never lead to decreases in what the agent knows. We explore various precise formulations of this principle, consider arguments in its favour, and explain how it interacts with different conceptions of evidence and accuracy. As we show, the principle has some (...) noteworthy consequences for the wider theory of knowledge. First, it implies that an agent cannot be justified in believing a set of mutually inconsistent claims. Second, it implies the existence of a kind of epistemic blindspot: it is not possible to know that one’s evidence is misleading. (shrink)

Capturing a scientific change in thinking about personality and individual differences that has been building over the past 15 years, this volume stands at an important moment in the development of psychology as a discipline. Rather than viewing individual differences as merely the raw material upon which selection operates, the contributing authors provide theories and empirical evidence which suggest that personality and individual differences are central to evolved psychological mechanisms and behavioral functioning. The book draws theoretical inspiration from life history (...) theory, evolutionary genetics, molecular genetics, developmental psychology, personality psychology, and evolutionary psychology, while utilizing the theories of the "best and the brightest" international scientists working on this cutting edge paradigm shift. In the first of three sections, the authors analyze personality and the adaptive landscape; here, the authors offer a novel conceptual framework for examining "personality assessment adaptations." Because individuals in a social environment have momentous consequences for creating and solving adaptive problems, humans have evolved "difference-detecting mechanisms" designed to make crucial social decisions such as mate selection, friend selection, kin investment, coalition formation, and hierarchy negotiation. In the second section, the authors examine developmental and life-history theoretical perspectives to explore the origins and development of personality over the lifespan. The third section focuses on the relatively new field of evolutionary genetics and explores which of the major evolutionary forces--such as balancing selection, mutation, co-evolutionary arms races, and drift--are responsible for the origins of personality and individual differences. Existing as a seminal work in the newly emerging evolutionary psychology field, this book is a "must-read" for anyone invested in the development of psychology as a field. (shrink)

This paper offers a new account of metaphysical explanation. The account is modelled on Kitcher’s unificationist approach to scientific explanation. We begin, in Sect. 2, by briefly introducing the notion of metaphysical explanation and outlining the target of analysis. After that, we introduce a unificationist account of metaphysical explanation before arguing that such an account is capable of capturing four core features of metaphysical explanations: irreflexivity, non-monotonicity, asymmetry and relevance. Since the unificationist theory of metaphysical explanation inherits irreflexivity and non-monotonicity (...) directly from the unificationist theory of scientific explanation that underwrites it, we focus on demonstrating how the account can secure asymmetry and relevance. (shrink)

According to a number of approaches in theoretical physics, spacetime does not exist fundamentally. Rather, spacetime exists by depending on another, more fundamental, non-spatiotemporal structure. A prevalent opinion in the literature is that this dependence should not be analyzed in terms of composition. We should not say, that is, that spacetime depends on an ontology of non-spatiotemporal entities in virtue of having them as parts. But is that really right? On the contrary, we argue that a mereological approach to dependent (...) spacetime is not only viable, but promises to enhance our understanding of the physical situation. (shrink)

Sam Harris dismantles the most common justification for religious faith--that a moral system cannot be based on science.

It is often claimed that pre-attentive vision has an ‘iconic’ format. This is seen to explain pre-attentive vision's characteristically high processing capacity and to make sense of an overlap in the mechanisms of early vision and mental imagery. But what does the iconicity of pre-attentive vision amount to? This paper considers two prominent ways of characterising pre-attentive visual icons and argues that neither is adequate: one approach renders the claim ‘pre-attentive vision is iconic’ empirically false while the other obscures its (...) ability to do the explanatory work, which motivates positing pre-attentive visual icons in the first place. With this noted, I introduce the notion of an ‘Analogue Map’ and argue that it provides a superior characterisation of pre-attentive vision's iconicity. I then argue that this forces a reassessment of debates which have traditionally presupposed the iconicity of pre-attentive vision, emphasising ramifications for the viability of a format-based perception-thought border. (shrink)

Time is woven into the fabric of our lives. Everything we do, we do in and across time. It is not just that our lives are stretched out in time, from the moment of birth to the moment of our death. It is that our lives are stories. We make sense of ourselves, today, by understanding who we were yesterday, and the day before, and the day before that; by understanding what we did and why we did it. Our memories (...) shape our present selves, since we are the product of who we were, and who we remember being. Yet who we are lasts for but a moment. It is who we will be that demands attention. We are forever projecting ourselves into the future. We painstakingly plan for the needs of our future selves, all the while knowing that while what we do will make those future selves who they are, still, our future selves are elusive. So it is not simply that we happen to live our lives in time, the way, say, one might happen to live in Australia, or Singapore. It is hard to fathom how things could be otherwise. What would it be to live a life without time? Yet time itself is intangible. Though we are keenly aware of what has been ‒ of pain and loss, regret and pride ‒ and of what might be ‒ of anticipation, and dread, and longing ‒ time itself seems unaffected by anything we do. Though we can anticipate a future birthday cake, time itself cannot be tasted. Though we can dread a future dentist’s appointment, time itself cannot be touched. Though we remember the crunching of leaves this past autumn, time itself cannot be heard. How can it be that something so central to each of us, to who we are, and what we care about, can be so spectral? What, in the end, is time? Is time real, like a substance in which each of us, like insects in amber, finds ourselves trapped? Is time a dimension through which we can move? Is time not a thing at all, but some connection between events? If time is real, what is it like? Does it flow like a river, taking each of us prisoner in its current, washing us ever closer to the end of our lives? Is time like a cresting wave, coming ever closer to each of us from the future, engulfing us, and then receding into the past? Or is time static? Like a one-way road that each of us might wander, with no chance to turn back? Or perhaps time is like none of these things. Perhaps time is more like space; something we can navigate freely, so that we can visit different times just like we visit different places. Perhaps we can we travel in time the way we can travel in space. These questions, and many more, are the focus of this book. Now, you might wonder what philosophers are doing writing a book about time. Surely that’s a job for physicists! It is true: a great deal of what we know about time stems from our understanding of physics. However, even in physics we find that there are questions about time that go unanswered. Moreover, increasingly, physicists are turning to philosophers for help in understanding the role that time plays in current physical theories. Our goal is to get the reader up to speed on some of the central issues that influence our understanding of time so that they too may play a role in this ongoing discussion between science and philosophy. We hope that in doing so it will become clear what philosophy can bring to the study of time. There is a natural narrative in philosophy regarding the study of time, and we have chosen to organise this book according to that narrative. However, the book may also be approached in a ‘choose-your-own adventure’ spirit. While later chapters build on material introduced in earlier chapters, you can skip around, reading the book in any order you choose. For the instructor, this means that she can design her course around this book in any number of ways, depending on the particular topic she wishes to focus on. (shrink)