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.

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)

Band 1. Von Augustinus bis Nietzsche -- Band 2. Das 20. Jahrhundert.

Martin Heideggers Denken nach 1938 ist vor allem durch drei grosse Themen gepragt: den Wandel des Menschenbildes, die Einfuhrung eines neuen Begriffes vom Denken und den Nachweis, dass Sein Seyn in Beziehung ist. Dabei stutzt er sich auf das Denken Franz Rosenzweigs, das bereits in der Formulierung von Sein und Zeit erkennbar ist, in den Schriften der 40er und 50er Jahre aber in besonders intensiver Weise nachwirkt. Ausgehend von dieser Zusammenschau von Heideggers und Rosenzweigs Denken zeichnet sich auch eine neue (...) Bewertung des Denkens von Emmanuel Levinas ab. (shrink)

The experiences described in the VIP transcripts are incredibly varied and yet frequently explicitly labelled by participants as "voices." How can we make sense of this? If we reflect carefully on uses of the word "voice", we see that it can express at least two entirely different concepts, which pick out categorically different phenomena. One concept picks out a speech sound (e.g. "This synthesizer has a "voice" setting"). Another concept picks out a specific agent (e.g. "I hear two voices: one (...) is a ten year-old boy…"). This chapter explores how these two concepts are related to one another in the context of voice-hearing. (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)

Jerry Fodor wrote the following assessment of Danto’s importance in 1993: “Danto has done something I’ve been very much wanting to do: namely, reconsider some hard problems in aesthetics in the light of the past 20 years or so of philosophical work on intentionality and representation” (Fodor 1993, p. 41). Fodor is absolutely right: some of Danto’s work could be thought of as the application of some influential ideas about perception that Fodor also shared. The problem is that these ideas (...) have turned out to be false. Both Danto and Fodor are modularist: they both think that perception is an encapsulated process that is in no way influenced by any kind of non-perceptual processing (see, e.g., Fodor 1983, Pylyshyn 1984). Many of Danto’s famous and influential arguments rely very directly on this modularist assumption. There is now, however, a wealth of evidence against modularism of the strong kind held to by Danto and Fodor. We now know that perceptual experience is not determined entirely by the retinal input: our visual processing is influenced at various point in a top-down manner. What we know and what kinds of visual stimuli we have encountered previously deeply influence how the retinal input is processed. The empirical literature on this is vast and conclusive (for an overview, see Teufel and Nanay 2017 but see also the references in the last section of this paper). What does this mean for Danto’s views on art and perception? While one of Danto’s premises may turn out to be false, the history and examples he gave are valuable and bear repeating. Even more importantly, Danto’s aesthetics can in part be separated out from his modularism, leading us to draw slightly different but arguably even more interesting conclusions from famous thought experiments such as the Gallery of Indiscernibles. (shrink)

Wie kann eine Theorie der Ethik beschaffen sein, wenn sie aus dem gedanklichen Repertoire der Existenzphilosophie entworfen wird? Sie bedarf vor allem einer speziellen Sprachfindung, die einen Diskurs mit zeitgenossischen Ethik-Konzeptionen im ersten Moment zu erschweren scheint. Susanne Mobua zeigt auf, dass dieses nicht zwangslaufig gilt, wenn der strukturelle Rahmen, in dem die Ethik der Existenz sich artikulieren kann, in die Untersuchung einbezogen wird. Hier kommt das Konzept des Neuen Denkens zum Tragen, das 1925 von Franz Rosenzweig vorgestellt wurde. Zum (...) ersten Mal ist es moglich, die Bedeutung des Rosenzweig'schen Denkens fur die Entwicklung von Existenzphilosophie und Dekonstruktion darzustellen. (shrink)

Aus einer bestimmten Perspektive betrachtet, zeigt sich Martin Heideggers erste systematische Schrift "Sein und Zeit" als Konzeptualisierung des "Sterns der Erlosung" von Franz Rosenzweig. Diesen Befund gilt es anhand eines intensiven Vergleiches beider Texte zu bestatigen. Erganzend werden Heideggers Arbeiten uber rund zwanzig Jahre von seiner Dissertation bis zu den "Beitragen zur Philosophie" verfolgt, um die Phasen einer Rezeption zwischen Aneignung, Widerspruch und Negation rekonstruieren zu konnen, die in der Geschichte der westlichen Rationalitat ihresgleichen sucht. Denn es wird sichtbar, wie (...) stark Heideggers Begrundung eines angeblichen seinsgeschichtlichen Auftrages der Deutschen von jenen Aussagen Franz Rosenzweigs gepragt ist, in denen dieser das judische Volk charakterisiert. Ein vertiefender Blick auf das Selbstverstandnis Martin Heideggers zur Zeit des Nationalsozialismus wird moglich, der dazu beitragen kann, die Frage seiner ideologischen Positionierung vor neuem Hintergrund zu stellen. (shrink)

Hume notoriously pursues a constructive science of human nature in the Treatise while raising serious skeptical doubts about that project and leaving them apparently unanswered. On the perspectivalist reading, Hume endorses multiple incommensurable epistemic perspectives in the Treatise. This reading faces two significant objections: that it renders Hume’s epistemology inconsistent (or at least highly incoherent) and that it is ad hoc. In this paper, I propose a perspectivalist account of epistemic justification in the Treatise that addresses, to a significant degree, (...) these concerns. Hume has available to him an account – what I will call epistemic dispositionalism – that is internally consistent, allows for epistemic continuity between perspectives, and is thoroughly grounded in his naturalism. (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)

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.

Renewing existentialism -- Existentialist legacies -- After God, after nature -- Remaining exposed -- Roundness -- Interlude -- After humanism -- Looking good -- Becoming worldly -- Askesis: shut up and train! -- Indications of an axial age -- Coda.

This paper uses detailed art criticism to ground a distinctive take on debates about the interaction of moral and aesthetic value. Immoralists claim that moral flaws can make artworks aesthetically better than they would otherwise be. I argue that whether or not immoralism is true, immoralists have not provided compelling characterizations of strategies that might constitute this kind of “immoral artistry.” The main exception is found in the work of A. W. Eaton. I critique Eaton’s perspective by way of sustained (...) interpretive-philosophical discussion of The Wire and especially The Sopranos. The discussion has implications for value interaction debates, conceptualizations of the “rough hero” genre, theories of appropriate response to fictions, and more applied debates about the moral criticism of film and television. (shrink)

In this paper, I will present and advocate a view about what we are doing when we attribute delusion, namely, say that someone is delusional. It is an “expressivist” view, roughly analogous to expressivism in meta-ethics. Just as meta-ethical expressivism accounts for certain key features of moral discourse, so does this expressivism account for certain key features of delusion attribution. And just as meta-ethical expressivism undermines factualism about moral properties, so does this expressivism, if correct, show that certain attempts to (...) objectively define delusion are misguided. I proceed as follows. I start by examining different attempts at defining delusion, separating broadly psychiatric attempts from epistemic ones. I then present a change of approach, according to which we question whether the term “delusion” is in the business of (merely) describing reality. I then support this proposal, first, by borrowing standard lines of argument from meta-ethics (including ontological reluctance, intrinsic motivation, and deep disagreement) but also, by inference to the best explanation of some the features we see when we try to theorise about delusion (namely that it is hard to define, and that our delusion attributions are elicited by a plurality of norms). (shrink)

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

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)

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)

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)