TY - JOUR
T1 - Unbounded hardware is equivalent to deterministic turing machines
AU - Chazelle, Bernard
AU - Monier, Louis
N1 - Funding Information:
* Tllis research was supported in part by the Defense Advanced Research Project Agency under contract F33615-78-C-1551, monitored by the Air Force Office of Scientific Research.
PY - 1983/7
Y1 - 1983/7
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=48749145588&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=48749145588&partnerID=8YFLogxK
U2 - 10.1016/0304-3975(83)90044-0
DO - 10.1016/0304-3975(83)90044-0
M3 - Article
AN - SCOPUS:48749145588
SN - 0304-3975
VL - 24
SP - 123
EP - 130
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 2
ER -