arXiv Open Access 2015

Efficient Computation by Three Counter Machines

Holger Petersen

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.CC

Penulis (1)

Holger Petersen

Format Sitasi

APA MLA BibTeX

Petersen, H. (2015). Efficient Computation by Three Counter Machines. https://arxiv.org/abs/1501.02212

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2015
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓