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)

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

Sam Buss produced the first polynomial size Frege proof of thepigeonhole principle. We introduce a variation of that problem and producea simpler proof based on parity. The proof appearing here has an upperbound that is quadratic in the size of the input formula.

This text addresses the profound human questions of love and work. Beginning with a historical introduction, the author progresses through adaptive problems that humans face, and concludes by showing how evolutionary psychology encompasses all branches of psychology.

A Kripke model ? is a submodel of another Kripke model ℳ if ? is obtained by restricting the set of nodes of ℳ. In this paper we show that the class of formulas of Intuitionistic Predicate Logic that is preserved under taking submodels of Kripke models is precisely the class of semipositive formulas. This result is an analogue of the Łoś-Tarski theorem for the Classical Predicate Calculus.In Appendix A we prove that for theories with decidable identity we can take (...) as the embeddings between domains in Kripke models of the theory, the identical embeddings. This is a well known fact, but we know of no correct proof in the literature. In Appendix B we answer, negatively, a question posed by Sam Buss: whether there is a classical theory T, such that ℋT is HA. Here ℋT is the theory of all Kripke models ℳ such that the structures assigned to the nodes of ℳ all satisfy T in the sense of classical model theory. (shrink)

To be autonomous is to be a law to oneself; autonomous agents are self-governing agents. Most of us want to be autonomous because we want to be accountable for what we do, and because it seems that if we are not the ones calling the shots, then we cannot be accountable. More importantly, perhaps, the value of autonomy is tied to the value of self-integration. We don't want to be alien to, or at war with, ourselves; and it seems that (...) when our intentions are not under our own control, we suffer from self-alienation. What conditions must be satisfied in order to ensure that we govern ourselves when we act? Philosophers have offered a wide range of competing answers to this question. (shrink)

The central theoretical issue of Wegner's book is: Why do we have the illusion of conscious will? I suggest that learning requires belief in the autonomy of action. You should believe in freedom of the will because if you have it you're right, and if you don't have it you couldn't have done otherwise anyway. —Sam Buss (Lecture at University of California, San Diego, 2000).

This volume contains articles covering a broad spectrum of proof theory, with an emphasis on its mathematical aspects. The articles should not only be interesting to specialists of proof theory, but should also be accessible to a diverse audience, including logicians, mathematicians, computer scientists and philosophers. Many of the central topics of proof theory have been included in a self-contained expository of articles, covered in great detail and depth. The chapters are arranged so that the two introductory articles come first; (...) these are then followed by articles from core classical areas of proof theory; the handbook concludes with articles that deal with topics closely related to computer science. (shrink)

Let T be a first-order theory. A T-normal Kripke structure is one in which every world is a classical model of T. This paper gives a characterization of the intuitionistic theory T of sentences intuitionistically valid in all T-normal Kripke structures and proves the corresponding soundness and completeness theorems. For Peano arithmetic , the theory PA is a proper subtheory of Heyting arithmetic , so HA is complete but not sound for PA-normal Kripke structures.

We study the long-standing open problem of giving$\forall {\rm{\Sigma }}_1^b$separations for fragments of bounded arithmetic in the relativized setting. Rather than considering the usual fragments defined by the amount of induction they allow, we study Jeřábek’s theories for approximate counting and their subtheories. We show that the$\forall {\rm{\Sigma }}_1^b$Herbrandized ordering principle is unprovable in a fragment of bounded arithmetic that includes the injective weak pigeonhole principle for polynomial time functions, and also in a fragment that includes the surjective weak pigeonhole (...) principle for FPNPfunctions. We further give new propositional translations, in terms of random resolution refutations, for the consequences of$T_2^1$augmented with the surjective weak pigeonhole principle for polynomial time functions. (shrink)

In the context of a largely exploratory inquiry, I warn against oversimplifying the relationships among intuitions, emotions, principle-governed reasoning, and responsiveness to reasons. I point out that one cannot determine the normative status of some fact without determining whether a case can be made for this status. But I also note that, though reason is thus autonomous, every episode of reasoning depends causally on the way things nonnormatively are, and this makes it possible for any reasoner to challenge even her (...) most basic normative assumptions. (shrink)

Almost all philosophers agree that a necessary condition on lying is that one says what one believes to be false. But, philosophers haven’t considered the possibility that the true requirement on lying concerns, rather, one’s degree-of-belief. Liars impose a risk on their audience. The greater the liar’s confidence that what she asserts is false, the greater the risk she’ll think she’s imposing on the dupe, and, therefore, the greater her blameworthiness. From this, I arrive at a dilemma: either the belief (...) requirement is wrong, or lying isn’t interesting. I suggest an alternative necessary condition for lying on a degree-of-belief framework. (shrink)

Intentional action involves both a series of neural events in the motor areas of the brain, and also a distinctive conscious experience that ''I'' am the author of the action. This paper investigates some possible ways in which these neural and phenomenal events may be related. Recent models of motor prediction are relevant to the conscious experience of action as well as to its neural control. Such models depend critically on matching the actual consequences of a movement against its internally (...) predicted effects. However, it remains unclear whether our conscious experience of action depends on a precise matching process, or a retrospective inference that ''I'' must have been responsible for a particular event. We report an experiment in which normal subjects judged the perceived time of either intentional actions, involuntary movements, or subsequent effects (auditory tones) of these. We found that the subject's intention to produce the auditory tone produced an intentional binding between the perceived times of the subject's action and the tone. However, if the intention was interrupted by an imposed involuntary movement, followed by the identical tone, no such binding occurred. The phenomenology of intentional action requires an appropriate predictive link between intentions and effects, rather than a retrospective inference that ''I'' caused the effect. (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)