scientific article
From MaRDI portal
Publication:3800030
zbMath0654.03043MaRDI QIDQ3800030
Publication date: 1986
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
realizabilitypolynomial time hierarchycomputable functionals of higher typeintuitionistic first order arithmeticintuitionistic number theory
Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Functionals in proof theory (03F10)
Related Items (49)
A strong induction scheme that leads to polynomially computable realizations ⋮ Arithmetical definability and computational complexity ⋮ On efficiency of notations for natural numbers ⋮ Unprovability of consistency statements in fragments of bounded arithmetic ⋮ A feasible theory of truth over combinatory algebra ⋮ Circuit principles and weak pigeonhole variants ⋮ An algebra and a logic for \(NC^ 1\) ⋮ Relating the bounded arithmetic and polynomial time hierarchies ⋮ Semantics vs syntax vs computations: Machine models for type-2 polynomial-time bounded functionals ⋮ On constructivity and the Rosser property: a closer look at some Gödelean proofs ⋮ Friedman-reflexivity ⋮ Structural properties for feasibly computable classes of type two ⋮ On parallel hierarchies and \(R_k^i\) ⋮ Intuitionistic formal theories with realizability in subrecursive classes ⋮ Completeness proofs for propositional logic with polynomial-time connectives ⋮ Graded multicategories of polynomial-time realizers ⋮ Deterministic summation modulo \(\mathcal B_{n}\), the semigroup of binary relations on \(0,1, \dots, n-1\) ⋮ \(\Delta\)-languages for sets and LOGSPACE computable graph transformers ⋮ Finitely axiomatized theories lack self‐comprehension ⋮ On feasible numbers ⋮ Computation models and function algebras ⋮ Expressing computational complexity in constructive type theory ⋮ Type 2 polynomial hierarchies ⋮ Transductions in arithmetic ⋮ Taking the Pirahã seriously ⋮ A note on SAT algorithms and proof complexity ⋮ Unnamed Item ⋮ Build your own clarithmetic I: Setup and completeness ⋮ Introduction to clarithmetic. I ⋮ Circuit lower bounds in bounded arithmetics ⋮ A new proof of the weak pigeonhole principle ⋮ Bounded arithmetic for NC, ALogTIME, L and NL ⋮ Bounded linear logic: A modular approach to polynomial-time computability ⋮ Functional interpretations of feasibly constructive arithmetic ⋮ Provably recursive functions of constructive and relatively constructive theories ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Logics for reasoning about cryptographic constructions ⋮ A proof-theoretic characterization of the basic feasible functionals ⋮ Elementary arithmetic ⋮ Proof Complexity of Non-classical Logics ⋮ On some formalized conservation results in arithmetic ⋮ Definability, decidability, complexity ⋮ A note on complexity measures for inductive classes in constructive type theory ⋮ The polynomial hierarchy of functions and its levels ⋮ Quantum implicit computational complexity ⋮ Bounded arithmetic, proof complexity and two papers of Parikh ⋮ Hereditarily-finite sets, data bases and polynomial-time computability ⋮ Applicative theories for logarithmic complexity classes ⋮ Introduction to clarithmetic. II
This page was built for publication:
