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

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)

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)

Excerpt from Die Weltanschauungen der Großen Philosophen der Neuzeit Der Hufforberung, Die I'leuauflage Diefes mit Beifall aufgenomme nen Büchleins 3u beforgen, glaubte ich mich um fo weniger ent3iehen 3u fallen, als mich mit Dem früh verftorbenen Derfaffer manche the meinfamieit Der über3eugung verbanb. Ba Der bisherige Umfang nicht wefenilüh uberfchritten werben follie, habe ich mich Darauf bee fchränit, Die bio; unb bibliographifchen Eingaben 3u revibieren, ein paar £iteraturvermerie hin3u3ufügen fowie einige ftiliftifche mängel3u befeitigen. Ilm übrigen erforberte Die Dietat Beibehaltung Des (...) Gertes auch Dort, wo Dem Derfaffer Die verantwortung überlaffen bleiben muß. Nur an wenigen Stellen habe ich eine. Durch Die Buchftaben R. 5. Als von mir herrührenb geienn3eichnete - Elnmeriung beigefügt. About the Publisher Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works. (shrink)

Seit dem 2. nachchristlichen Jahrhundert werden die Schriften von Aristoteles kommentiert. Diese Ausgabe enthält griechische Kommentare zu seinem Werk vom 3. bis 8. Jahrhundert n. Chr., u. a. von Alexander von Aphrodiensias, Themistios, Joh. Philoponus, Simplicius in griechischer Sprache.

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.

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.

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)

A number of philosophers have argued in favour of extended simples on the grounds that they are needed by fundamental physics. The arguments typically appeal to theories of quantum gravity. To date, the argument in favour of extended simples has ignored the fact that the very existence of spacetime is put under pressure by quantum gravity. We thus consider the case for extended simples in the context of different views on the existence of spacetime. We show that the case for (...) extended simples based on physics is far more complex than has been previously thought. We present and then map this complexity, in order to present a much more textured picture of the argument for extended simples. (shrink)

One of the major difficulties facing presentism is the problem of causation. In this paper, I propose a new solution to that problem, one that is compatible with intrinsic, fundamental causal relations. Accommodating relations of this kind is important because (i) according to David Lewis (2004), such relations are needed to account for causation in our world and worlds relevantly similar to our own, (ii) there is no other strategy currently available that successfully reconciles presentism with relations of this kind (...) and (iii) resolving the problem of causation by accommodating intrinsic, fundamental causal relations provides the presentist with a far more general solution to the problem of causation than those currently on offer. (shrink)

Work in quantum gravity suggests that spacetime is not fundamental. Rather, spacetime emerges from an underlying, non-spatiotemporal reality. After clarifying the type of emergence at issue, I argue that standard conceptions of emergence available in metaphysics won’t work for the emergence of spacetime. I go on to consider spacetime functionalism as a way to make sense of spacetime emergence. I argue that a functionalist approach to spacetime modelled on mental state functionalism is not a viable alternative to the standard conception (...) of emergence in metaphysics. I go on to consider an alternative: ‘partial’ functionalism, whereby certain aspects of spacetime are functionalised, rather than spacetime as a whole. (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.

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.

Seit dem 2. nachchristlichen Jahrhundert werden die Schriften von Aristoteles kommentiert. Diese Ausgabe enthält griechische Kommentare zu seinem Werk vom 3. bis 8. Jahrhundert n. Chr., u. a. von Alexander von Aphrodiensias, Themistios, Joh. Philoponus, Simplicius in griechischer Sprache.

Commentaries on Aristotle's writings have been produced since the 2nd century AD. This edition contains Greek commentaries on his work from the 3rd to the 8th centuries AD by, among others, Alexander of Aphrodiensias, Themistios, Joh. Philoponus, Simplicius in Greek.

Seit dem 2. nachchristlichen Jahrhundert werden die Schriften von Aristoteles kommentiert. Diese Ausgabe enthält griechische Kommentare zu seinem Werk vom 3. bis 8. Jahrhundert n. Chr., u. a. von Alexander von Aphrodiensias, Themistios, Joh. Philoponus, Simplicius in griechischer Sprache.