1 citations · 2 across the 3 of their papers we have counts for
6 papers
A note on the complexity of addition
Emil Jeřábek
We show that the sum of a sequence of integers can be computed in linear time on a Turing machine. In particular, the most obvious algorithm for this problem, which appears to requ…
A simplified lower bound for implicational logic
Emil Jeřábek
We present a streamlined and simplified exponential lower bound on the length of proofs in intuitionistic implicational logic, adapted to Gordeev and Haeusler's dag-like natural de…
Models of as exponential integer parts
Emil Jeřábek
We prove that (additive) ordered group reducts of nonstandard models of the bounded arithmetical theory are recursively saturated in a rich language with predicate…
Iterated multiplication in
Emil Jeřábek
We show that , the basic theory of bounded arithmetic corresponding to the complexity class , proves the axiom expressing the totality of iterated mult…
On the proof complexity of logics of bounded branching
Emil Jeřábek
We investigate the proof complexity of extended Frege (EF) systems for basic transitive modal logics (K4, S4, GL, ...) augmented with the bounded branching axioms .…
On the complexity of the clone membership problem
Emil Jeřábek
We investigate the complexity of the Boolean clone membership problem (CMP): given a set of Boolean functions and a Boolean function , determine if is in the clone gener…