<p>I am a software engineer and I need a bit of clarification. The practical performance of algorithms is usually compared against models where arithmetic and dereferencing are instantaneous, such as RAM. The assumption is that the primary storage  already has the capacity to store and address the input, so it should be feasible to expect rapid performance on the words that encode the address space. This is reasonable, yet I think that the model may give equal footing to algorithms that perform inherently different amounts of work - such as returning a constant and mapping numbers (the latter is obviously more demanding in a non-Neumann architecture). Similarly, on a tangent topic, the development of parallel algorithms assumes infinitely parallel hardware, which does not take into account the spatial factors involved in a circuit design.</p>

<p>Furthermore, while contemporary machines provide integer-based addressing and while I see this as an arbitrary beneficial phenomenon, I don't think that there is fundamental need for our addresses to be effective quantities, with the corresponding constant-time arithmetic operations on them. So this may also influence the analysis of algorithms towards disbalance.</p>

<p>In view of the above, I have the following questions:</p>

<ol>
<li>Are there operations, to our understanding, that we expect to be implemented efficiently in our fully featured (i.e. for practical evaluation) models of computation and why - arithmetic, or any polylogarithmic complexity operation (assuming the standard encodings), or any function that maps words, even finding the n-th prime number if it fits in a word. Why we choose particular operations, and could we choose others? Can we use a different encoding, not based on positional numerals as the medium of computation and gain some comparative benefits throughout?</li>
<li>Is it conceivable that data structures and algorithms may be improved asymptotically if they were implemented directly as VLSI circuit designs? For example, is it theoretically conceivable that sorting and dynamic indexing (single-, multi-dimensional) of sets with variably-sized lexicographically ordered keys can be implemented more efficiently if we don't use RAM as our point of reference? Is there counterproof to that, proof, or conjecture?</li>
<li>If improvements appear to be possible under 2, how the relationship between the model and the problem enable such improvements? For example, given a universe of keys for an indexing problem, how can we decide if a given model of computation (restricted by faithful correspondence to the VLSI design economics) is optimal, or a better model of computation exists (again feasible and faithful to VLSI economics, but different operations and implementation)?</li>
</ol>

<p>Thanks</p>

<p><strong>PS:</strong>
A similar issue with lock-free algorithms in my opinion is that they assume the underlying architecture provides atomic operations that scale perfectly with the number of cores and cpus. The interconnects and coherency protocols can not scale perfectly, so essentially the algorithms remain blocking. The algorithmic design optimally solves the problem with the resources provided by the model, but this does not answer which is the most optimal practically feasible hardware architecture for solving the original problem, and whether from this point of view the algorithm is actually optimal.</p>

CC BY-SA 3.0
2013-12-14T19:30:57.410Z
These are good questions, but difficult to answer quickly. In short, (1) encoding matters and can make a huge difference, especially if you assume certain operations are "cheap" (2) changing the model of computation can definitely improve things asymptotically (like from one poly to a smaller poly) (3) we see this in sorting, where in a comparison model n log n operations are needed, but in a RAM model you can get around this.
Suresh Venkat
CC BY-SA 3.0
2013-12-14T21:19:32.163Z
@Suresh The comparison model is very abstract. Essentially, I wonder if there are circuit design schemata that respect real-world issues like space constraints and such, that can provide solutions to specific problems that outperform asymptotically their RAM-optimized counterparts running on optimal circuit implementation of a RAM machine. I ask of the kind of design choices could result in such performance benefits - like encodings, instruction set, etc. and how a suboptimal for a problem model can be recognized without trying all possible model VLSI implementation-solution configurations.
simeonz
CC BY-SA 3.0
2013-12-15T02:05:41.987Z
simeonz: It is widely (universally?) believed that no *hardware* improvement will result a polynomial-time solution to a problem that was previously only implementable in exponential time. The caveats to that statement are quantum computing and massive parallelization (i.e. parallelization that grows with the size of the input). However, differences in polynomials (like $n^3$ to $n^2$) can definitely be hardware-model-dependent.
usul
CC BY-SA 3.0
2013-12-15T06:47:48.817Z
@usul So you are saying that it is theoretically conceivable that changing the circuit implementation from RAM-like to something else can enable improvements in the asymptotic performance? Can someone provide any references or a field of tcs that deals with this particular aspect formally. I am not theoretically savvy enough to guess it. (Preferably the changes should not arbitrarily increase the size of the circuit, but any theoretic treatment would be great.)
simeonz
CC BY-SA 3.0
2013-12-15T13:51:26.353Z
Sorry, I'm not at all an expert and don't know any references. But if by improve asymptotic performance you mean from one polynomial time like $n^3$ to another like $n^2$, then definitely it's possible.
usul
CC BY-SA 3.0
2013-12-16T01:55:38.317Z
some of this relates to the ["uniform vs nonuniform"](http://en.wikipedia.org/wiki/Circuit_complexity#Uniformity) question in circuits [mostly open]... you might also look into ["cache oblivious algorithms"](http://en.wikipedia.org/wiki/Cache-oblivious_algorithm) for another theoretical take on it all. related, there is also an old paper by ? that shows that factoring can be done in polynomial number of arithmetic operations, but with large numbers. [does anyone recall that ref?]
vzn
CC BY-SA 3.0
2013-12-16T08:30:17.317Z
@vzn I confess that I did not pose any proper requirements on the circuits, but I am just a wannabe as far as tcs goes. From what I understand fro Wikipedia, the uniformity ensures that there is a concise and computable schemata for the circuit. But for me, the most important constraint is to associate cost with the distance between the nodes. We can relate the distance between any two nodes in the graph embedding of the circuit's graph to the unit distance, which I presume should be smallest distance between two nodes. Admittedly improvising, but the point is to restrict the density.
simeonz
CC BY-SA 3.0
2013-12-16T08:37:22.267Z
@vzn It is true that cache oblivious algorithms are naturally more suitable to hardware implementation, but it is a different kind of result. I would have hoped for something that generalizes such results. I will look for the factoring paper that you mention - I assume circuit implementation was used? Thanks.
simeonz
<ds.algorithms><circuit-complexity><time-complexity>
Fundamental assumptions in complexity analysis
simeonz
# Fundamental assumptions in complexity analysis

(Asked by: username_0 on 2013-12-14)

I am a software engineer and I need a bit of clarification. The practical performance of algorithms is usually compared against models where arithmetic and dereferencing are instantaneous, such as RAM. The assumption is that the primary storage already has the capacity to store and address the input, so it should be feasible to expect rapid performance on the words that encode the address space. This is reasonable, yet I think that the model may give equal footing to algorithms that perform inherently different amounts of work - such as returning a constant and mapping numbers (the latter is obviously more demanding in a non-Neumann architecture). Similarly, on a tangent topic, the development of parallel algorithms assumes infinitely parallel hardware, which does not take into account the spatial factors involved in a circuit design.

Furthermore, while contemporary machines provide integer-based addressing and while I see this as an arbitrary beneficial phenomenon, I don't think that there is fundamental need for our addresses to be effective quantities, with the corresponding constant-time arithmetic operations on them. So this may also influence the analysis of algorithms towards disbalance.

In view of the above, I have the following questions:

1. Are there operations, to our understanding, that we expect to be implemented efficiently in our fully featured (i.e. for practical evaluation) models of computation and why - arithmetic, or any polylogarithmic complexity operation (assuming the standard encodings), or any function that maps words, even finding the n-th prime number if it fits in a word. Why we choose particular operations, and could we choose others? Can we use a different encoding, not based on positional numerals as the medium of computation and gain some comparative benefits throughout?
2. Is it conceivable that data structures and algorithms may be improved asymptotically if they were implemented directly as VLSI circuit designs? For example, is it theoretically conceivable that sorting and dynamic indexing (single-, multi-dimensional) of sets with variably-sized lexicographically ordered keys can be implemented more efficiently if we don't use RAM as our point of reference? Is there counterproof to that, proof, or conjecture?
3. If improvements appear to be possible under 2, how the relationship between the model and the problem enable such improvements? For example, given a universe of keys for an indexing problem, how can we decide if a given model of computation (restricted by faithful correspondence to the VLSI design economics) is optimal, or a better model of computation exists (again feasible and faithful to VLSI economics, but different operations and implementation)?

Thanks

**PS:**
A similar issue with lock-free algorithms in my opinion is that they assume the underlying architecture provides atomic operations that scale perfectly with the number of cores and cpus. The interconnects and coherency protocols can not scale perfectly, so essentially the algorithms remain blocking. The algorithmic design optimally solves the problem with the resources provided by the model, but this does not answer which is the most optimal practically feasible hardware architecture for solving the original problem, and whether from this point of view the algorithm is actually optimal.

**Tags:** ds.algorithms, circuit-complexity, time-complexity

> **Comments:**
> **username_1**: These are good questions, but difficult to answer quickly. In short, (1) encoding matters and can make a huge difference, especially if you assume certain operations are "cheap" (2) changing the model of computation can definitely improve things asymptotically (like from one poly to a smaller poly) (3) we see this in sorting, where in a comparison model n log n operations are needed, but in a RAM model you can get around this.  
> **username_0**: @Suresh The comparison model is very abstract. Essentially, I wonder if there are circuit design schemata that respect real-world issues like space constraints and such, that can provide solutions to specific problems that outperform asymptotically their RAM-optimized counterparts running on optimal circuit implementation of a RAM machine. I ask of the kind of design choices could result in such performance benefits - like encodings, instruction set, etc. and how a suboptimal for a problem model can be recognized without trying all possible model VLSI implementation-solution configurations.  
> **username_2**: username_0: It is widely (universally?) believed that no *hardware* improvement will result a polynomial-time solution to a problem that was previously only implementable in exponential time. The caveats to that statement are quantum computing and massive parallelization (i.e. parallelization that grows with the size of the input). However, differences in polynomials (like $n^3$ to $n^2$) can definitely be hardware-model-dependent.  
> **username_0**: @username_2 So you are saying that it is theoretically conceivable that changing the circuit implementation from RAM-like to something else can enable improvements in the asymptotic performance? Can someone provide any references or a field of tcs that deals with this particular aspect formally. I am not theoretically savvy enough to guess it. (Preferably the changes should not arbitrarily increase the size of the circuit, but any theoretic treatment would be great.)  
> **username_2**: Sorry, I'm not at all an expert and don't know any references. But if by improve asymptotic performance you mean from one polynomial time like $n^3$ to another like $n^2$, then definitely it's possible.  
> **username_3**: some of this relates to the ["uniform vs nonuniform"](http://en.wikipedia.org/wiki/Circuit_complexity#Uniformity) question in circuits [mostly open]... you might also look into ["cache oblivious algorithms"](http://en.wikipedia.org/wiki/Cache-oblivious_algorithm) for another theoretical take on it all. related, there is also an old paper by ? that shows that factoring can be done in polynomial number of arithmetic operations, but with large numbers. [does anyone recall that ref?]  
> **username_0**: @username_3 I confess that I did not pose any proper requirements on the circuits, but I am just a wannabe as far as tcs goes. From what I understand fro Wikipedia, the uniformity ensures that there is a concise and computable schemata for the circuit. But for me, the most important constraint is to associate cost with the distance between the nodes. We can relate the distance between any two nodes in the graph embedding of the circuit's graph to the unit distance, which I presume should be smallest distance between two nodes. Admittedly improvising, but the point is to restrict the density.  
> **username_0**: @username_3 It is true that cache oblivious algorithms are naturally more suitable to hardware implementation, but it is a different kind of result. I would have hoped for something that generalizes such results. I will look for the factoring paper that you mention - I assume circuit implementation was used? Thanks.  

---

## 0 answers

