Loading...
Please wait, while we are loading the content...
Similar Documents
On the Optimality of RAM Complexity
| Content Provider | Semantic Scholar |
|---|---|
| Author | Dershowitz, Nachum Falkovich, Evgenia |
| Copyright Year | 2013 |
| Abstract | We demonstrate that the programs of any classical (as opposed to parallel or interactive) computation model or programming language that satisfies natural postulates of effectiveness (which specialize Gurevich’s Sequential Postulates)—regardless of the data structures it employs—can be simulated by a random access machine (RAM) with only constant overhead. In essence, the effectiveness postulates assert the following: states can be represented as logical structures; transitions depend on a fixed finite set of terms (those referred to in the algorithm); basic operations can be programmed from constructors; and transitions commute with isomorphisms. Complexity for any domain is measured in terms of constructor operations. It follows that algorithmic lower bounds for the RAM model hold (up to a constant factor determined by the algorithm in question) for any and all effective classical models of computation, whatever its control structures and data structures. This substantiates the polynomial-time version of the classical extended Church-Turing Thesis (the Invariance Thesis), namely that every effective classical algorithm can be polynomially simulated by a Turing machine. 1998 ACM Subject Classification F.1.1 Models of Computation |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cs.tau.ac.il/~nachumd/papers/RAM.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
