Efficient Computation by Three Counter Machines

Holger Petersen

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 funct…