Efficient Computation by Three Counter Machines
classification
💻 cs.CC
keywords
countermachinesthreecomputablecomputationcontentscountersdeterministic
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.