Why is the addition function exponential for k-bit integers providing only zero, equality and the successor functions?
The complexity of getting "the result of a + b" would indeed "be O(b) starting from a".

However, b is a log(b)-bit integer, and O(b) = O(2^(log(b))).