Book contents
- Frontmatter
- Preface
- Opening speech of Petr Vopěnka
- Bolzano Medal awarded to Gaisi Takeuti
- Contents
- Collapsing Polynomial-Time Degrees
- Qualitative and Probabilistic Models of Full Belief
- Relative Splittings of in the-Enumeration Degrees
- A Realizability Interpretation for Classical Arithmetic
- An Axiomatization of Quantified Propositional Gödel Logic Using the Takeuti-Titani Rule
- Another Pathological Well-Ordering
- How Small Can the Set of Generics Be?
- Entailment Relations and Distributive Lattices
- The Friedberg Jump Inversion Theorem Revisited: A Study of Undefinable Cuts
- Hartley Rogers’ 1965 Agenda
- Liftings of Homomorphisms Between Quotient Structures and Ulam Stability
- Mathematical Fuzzy Logic – State of Art
- Reflections on the Last Delfino Problem
- Continuous Images of Coanalytic Sets
- Classification of Subsheaves over GL-Algebras
- On the Bit-Comprehension Rule
- Cardinal Invariants Associated with Predictors
- A Theorem on Countable Ordered Sets with an Application to Universal Graphs
- Dimension Theory and Smooth Stratification of Rigid Subanalytic Sets
- The Ramsey Structure of A-Determined Sets in a Saturated Universe
- On Definability of Admissible Sets
- Additive Theories
- Adding Multiplication to an O-minimal Expansion of the Additive Group of Real Numbers
- The Superjump in Martin-Löf Type Theory
- “Just Because”: Taking Belief Bases Seriously
- Artin Approximation via the Model Theory of Cohen-Macaulay Rings
- Ordinal Systems, Part 2: One Inaccessible
- Autonomous Fixed Point Progressions and Fixed Point Transfinite Recursion
- Finitary Reductions for Local Predicativity, I: Recursively Regular Ordinals
- The Complexity of Linear Logic with Weakening
- Some Remarks on the Maximality of Inner Models
- Author Index
- References
On the Bit-Comprehension Rule
Published online by Cambridge University Press: 31 March 2017
Book contents
- Frontmatter
- Preface
- Opening speech of Petr Vopěnka
- Bolzano Medal awarded to Gaisi Takeuti
- Contents
- Collapsing Polynomial-Time Degrees
- Qualitative and Probabilistic Models of Full Belief
- Relative Splittings of in the-Enumeration Degrees
- A Realizability Interpretation for Classical Arithmetic
- An Axiomatization of Quantified Propositional Gödel Logic Using the Takeuti-Titani Rule
- Another Pathological Well-Ordering
- How Small Can the Set of Generics Be?
- Entailment Relations and Distributive Lattices
- The Friedberg Jump Inversion Theorem Revisited: A Study of Undefinable Cuts
- Hartley Rogers’ 1965 Agenda
- Liftings of Homomorphisms Between Quotient Structures and Ulam Stability
- Mathematical Fuzzy Logic – State of Art
- Reflections on the Last Delfino Problem
- Continuous Images of Coanalytic Sets
- Classification of Subsheaves over GL-Algebras
- On the Bit-Comprehension Rule
- Cardinal Invariants Associated with Predictors
- A Theorem on Countable Ordered Sets with an Application to Universal Graphs
- Dimension Theory and Smooth Stratification of Rigid Subanalytic Sets
- The Ramsey Structure of A-Determined Sets in a Saturated Universe
- On Definability of Admissible Sets
- Additive Theories
- Adding Multiplication to an O-minimal Expansion of the Additive Group of Real Numbers
- The Superjump in Martin-Löf Type Theory
- “Just Because”: Taking Belief Bases Seriously
- Artin Approximation via the Model Theory of Cohen-Macaulay Rings
- Ordinal Systems, Part 2: One Inaccessible
- Autonomous Fixed Point Progressions and Fixed Point Transfinite Recursion
- Finitary Reductions for Local Predicativity, I: Recursively Regular Ordinals
- The Complexity of Linear Logic with Weakening
- Some Remarks on the Maximality of Inner Models
- Author Index
- References
- Type
- Chapter
- Information
- Logic Colloquium '98 , pp. 262 - 279Publisher: Cambridge University PressPrint publication year: 2000
References
. The permanent requires large uniform threshold circuits. To appear in Chicago Journal of Theoretical Computer Science. Preliminary Version appeared in COCOON'96, 1998.
, , and . On uniformity within NC1. Journal of Computer and System Sciences, 41:274–306, 1990.Google Scholar
. Bounded Arithmetic. Bibliopolis, Napoli, 1986.
. A first order theory for the parallel complexity class NC. Technical Report BCCS-89-01, Boston College, January 1989.
. On polynomial size Frege proofs of certain combinatorial principles. In and , editors, Arithmetic, Proof Theory and Computational Complexity, volume 23 of Oxford Logic Guides, pages 162–184. Clarendon Press, Oxford, 1993.
and . First order bounded arithmetic and small boolean circuit complexity classes. In and , editors, Feasible Mathematics II, pages 154–218. Birkhäuser, Boston, 1995.
. A bounded arithmetic theory for constant depth threshold circuits. In , editor, GÖDEL '96, pages 224–234, 1996. Springer Lecture Notes in Logic 6.
and . On proofs about threshold circuits and counting hierarchies (extended abstract). In Proc. 13th IEEE Symposium on Logic in Computer Science, pages 444–452, 1998.
. Bounded Arithmetic, Propositional Logic and Complexity Theory. Cambridge University Press, 1995.
, , and . Interactive computations of optimal solutions. In , editor, Mathematical Foundations of Computer Science, pages 48–60. Springer, 1990.
, , and . Bounded arithmetic and the polynomial hierarchy. Annals of Pure and Applied Logic, 52:143–153, 1991.Google Scholar
. Some relations between subsystems of arithmetic and complexity of computations. In , editor, Logic fromComputer Science, pages 499–519. Springer, New York, 1992.
. RSUV isomorphisms. In and , editors, Arithmetic, Proof Theory and Computational Complexity, volume 23 of Oxford LogicGuides, pages 364–386. Clarendon Press, Oxford, 1993.
- 6
- Cited by