35 citations · 115 across the 15 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2023
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…
cs.CC2019
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…
cs.CC2012★ 35 cited
Integer factoring and modular square roots
Emil Jeřábek
Buresh-Oppenheim proved that the NP search problem to find nontrivial factors of integers of a special form belongs to Papadimitriou's class PPA, and is probabilistically reducible…