Unbounded hardware is equivalent to deterministic turing machines

Bernard Chazelle, Louis Monier

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

The purpose of this paper is to investigate models of computation from a realistic viewpoint. We introduce the concept of physical computation as opposed to functional computation, and by referring to the laws of physics we study the basic criteria which a model of computation must meet in order to be realistic. With this formal apparatus, we define a very general, realistic model of planar, digital circuits, which allows for full parallelism. This model is especially well suited to describe systolic architectures. Actually, the assumption of planarity serves only practical purposes, and can be removed without altering our main results. We compare the complexity classes in this parallel model with those associated with sequential models such as the Deterministic Turing Machine (DTM) model. Our main result is that both models are space and time equivalent in the polynomial class. In particular, any circuit can be simulated in polynomial time on a DTM. One consequence is that unbounded hardware does not make NP-hardness tractable. We also address the issue of area-time tradeoffs and show that the area of a circuit can always be bounded by a polynomial function of the sequential time.

Original languageEnglish (US)
Pages (from-to)123-130
Number of pages8
JournalTheoretical Computer Science
Volume24
Issue number2
DOIs
StatePublished - Jul 1983
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Unbounded hardware is equivalent to deterministic turing machines'. Together they form a unique fingerprint.

Cite this