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

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)

It is often assumed that adaptation — a temporary change in sensitivity to a perceptual dimension following exposure to that dimension — is a litmus test for what is and is not a “primary visual attribute”. Thus, papers purporting to find evidence of number adaptation motivate a claim of great philosophical significance: That number is something that can be seen in much the way that canonical visual features, like color, contrast, size, and speed, can. Fifteen years after its reported discovery, (...) number adaptation’s existence seems to be nearly undisputed, with dozens of papers documenting support for the phenomenon. The aim of this paper is to offer a counterweight — to critically assess the evidence for and against number adaptation. After surveying the many reasons for thinking that number adaptation exists, we introduce several lesser-known reasons to be skeptical. We then advance an alternative account — the old news hypothesis — which can accommodate previously published findings while explaining various (otherwise unexplained) anomalies in the existing literature. Next, we describe the results of eight pre-registered experiments which pit our novel old news hypothesis against the received number adaptation hypothesis. Collectively, the results of these experiments undermine the number adaptation hypothesis on several fronts, whilst consistently supporting the old news hypothesis. More broadly our work raises questions about the status of adaptation itself as a means of discerning what is and is not a visual attribute. (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)

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)

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

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.

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)

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

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.

The visual system adapts to a wide range of visual features, from lower-level features like color and motion to higher-level features like causality and, perhaps, number. According to some, adaptation is a strictly perceptual phenomenon, such that the presence of adaptation licenses the claim that a feature is truly perceptual in nature. Given the theoretical importance of claims about adaptation, then, it is important to understand exactly when the visual system does and does not exhibit adaptation. Here, we take as (...) a case study one specific kind of adaptation: visual adaptation to size. Supported by evidence from four experiments, we argue that, despite robust effects of size adaptation in the lab, (1) size adaptation effects are phenomenologically underwhelming (in some cases, hardly appreciable at all), (2) some effects of size adaptation appear contradictory, and difficult to explain given current theories of size adaptation, and (3) prior studies on size adaptation may have failed to isolate size as the adapted dimension. Ultimately, we argue that while there is evidence to license the claim that size adaptation is genuine, size adaptation is a puzzling and poorly understood phenomenon. (shrink)

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

The (re)building of the post-communist states offers new perspectives both on the state and on the multiple transitions that followed communism. Specifically, it shifts our analytical focus from states as consolidated outcomes and unitary actors to the process by which states come into being and into action in the modern era. This process consists of elite competition over policy-making authority, which is shaped and constrained by existing institutional resources, the pacing of transformation, and the international context. The four ideal types (...) of state-building that result are exemplified by the post-communist experience: democratic, autocratic, fractious, and personalistic. (shrink)

According to the KK-principle, knowledge iterates freely. It has been argued, notably in Greco, that accounts of knowledge which involve essential appeal to normality are particularly conducive to defence of the KK-principle. The present article evaluates the prospects for employing normality in this role. First, it is argued that the defence of the KK-principle depends upon an implausible assumption about the logical principles governing iterated normality claims. Once this assumption is dropped, counter-instances to the principle can be expected to arise. (...) Second, it is argued that even if the assumption is maintained, there are other logical properties of normality which can be expected to lead to failures of KK. Such failures are noteworthy, since they do not depend on either a margins-for-error principle or safety condition of the kinds Williamson appeals to in motivating rejection KK. “Introduction: KK and Being in a Position to Know” Section formulates two versions of the KK-Principle; “Inexact Knowledge and Margins for Error” Section presents a version of Williamson’s margins-for-error argument against it; “Knowledge and Normality” and “Iterated Normality” Sections discuss the defence of the KK-Principle due to Greco and show that it is dependent upon the implausible assumption that the logic of normality ascriptions is at least as strong as K4; finally, “Knowledge in Abnormal Conditions” and “Higher-Order Ignorance Inside the Margins” Sections argue that a weakened version of Greco’s constraint on knowledge is plausible and demonstrate that this weakened constraint will, given uncontentious assumptions, systematically generate counter-instances to the KK-principle of a novel kind. (shrink)

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)

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)

This paper develops an account of pluralities based on the following simple claim: some things are nothing over and above the individual things they comprise. For some, this may seem like a mysterious statement, perhaps even meaningless; for others, like a truism, trivial and inferentially inert. I show that neither reaction is correct: the claim is both tractable and has important consequences for a number of debates in philosophy.

The popularity of ‘food sovereignty’ to cover a range of positions, interventions, and struggles within the food system is testament, above all, to the term’s adaptability. Food sovereignty is centrally, though not exclusively, about groups of people making their own decisions about the food system—it is a way of talking about a theoretically-informed food systems practice. Since people are different, we should expect decisions about food sovereignty to be different in different contexts, albeit consonant with a core set of principles. (...) In this paper we look at the analytical points of friction in applying ideas of food sovereignty within the context of Indigenous struggles in North America. This, we argue, helps to clarify one of the central themes in food sovereignty: that it is a continuation of anti-colonial struggles, even in post-colonial contexts. Such an examination has dividends both for scholars of food sovereignty and for those of Indigenous politics: by helping to problematize notions of food sovereignty and postcoloniality, but also by posing pointed questions around gender for Indigenous struggles. (shrink)

Some critics argue that the types of psychiatric diagnosis found in the Diagnostic and Statistical Manual of Mental Disorders and International Classification of Disease are superfluous and should be abandoned. These are known as categorical polythetic psychiatric diagnoses. To receive a categorical polythetic psychiatric diagnosis an individual need only exhibit some, rather than all, of the symptoms on the diagnostic criteria. Consequently, categorical polythetic psychiatric diagnoses only associate an individual with a range of symptoms rather than specify which symptoms they (...) have. Drawing on Giere’s account of scientific models, I portray categorical polythetic psychiatric diagnoses as abstract models that guide the building of less abstract models. These models can specify which symptoms a particular individual has. Additionally, categorical polythetic psychiatric diagnoses can guide investigation of symptoms towards difficult to spot symptoms, guide investigation towards changing symptoms, and guide investigation towards how symptoms manifest. These important roles mean categorical polythetic psychiatric diagnoses should not be abandoned. (shrink)

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)