2015/01/09 by Petersen, Holger
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1501.02212
We show that multiplication can be done in polynomial time on a three counter machine that receives its input as the contents of two counters. The technique is generalized to functions of two variables computable by deterministic Turing machines in linear space.