5
$\begingroup$

One of the main benefits of algorithm analysis, is that it offers asymptotic improvements to complexity as opposed to hardware, which offers only constant improvements. E.g switching to a super computer from a workstation might give a $\times 1,000,000$ increase in speed, but if that supercomputer is running a linear search on a sorted array, it will eventually be trumped by a desktop running a binary search for large enough problem sizes.

My question is this:

Are there any improvements in hardware(theoretical or practical) that could offer an asymptotic speedup over pre-existing hardware?

In this case pre-existing refers to at least 3rd generation computing technology. I'm not really interested in speedups over vacuum tubes.

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
6
$\begingroup$

Quantum computers, if they ever get built, will be asymptotically faster than existing computers in certain tasks. Limited quantum computers might already exist, though this is a contentious issue.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What's the speedup though? Polynomial or exponential? $\endgroup$
    – Tobi Alafin
    Commented Dec 31, 2016 at 9:43
  • 1
    $\begingroup$ Depends on the task. Quantum computing is a wide topic, and I am not going to summarize it in this answer. There is plenty of information about quantum "supremacy" on the internet. $\endgroup$
    – Yuval Filmus
    Commented Dec 31, 2016 at 9:44
6
$\begingroup$

Three-dimensional memory systems can improve the asymptotic complexity.

Suppose the CPU is in the center of the world, and the rest of the world is filled with memory cells. The CPU broadcasts a request to memory and waits a finite amount of time for a response.

If the memory is in the form of a 2-dimensional plane, then the CPU waiting $n$ nanoseconds can reach $\Theta(n^2)$ memory cells.

But if the memory is in the form of 3-dimensional space, then the CPU waiting the same $n$ nanoseconds can reach $\Theta(n^3)$ storage cells.

When a program needs to use $m$ memory cells for its execution, the 2D memory technology has a latency of $\Theta(\sqrt[2]{n})$ per operation, whereas the the 3D memory has a latency of $\Theta(\sqrt[3]{n})$.

Improve this answer
$\endgroup$
7
  • $\begingroup$ This sounds amazing. Why hasn't this been done yet? $\endgroup$
    – Tobi Alafin
    Commented Jan 1, 2017 at 7:44
  • $\begingroup$ @TobiAlafin Because the limiting factor is the number of gates, not the distance between CPU and memory. Actual memories are reached through a single bus; the number of cells that the CPU can access in time $n$ is $\theta(n)$, limited by the bandwidth of the bus, the address decoder and the refresh mechanism. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Jan 1, 2017 at 21:17
  • $\begingroup$ @Gilles I think a CPU can access more than $n$ cells in $n$ time. I think it can access $n^2$ cells because a request can spread out in 2D space. $\endgroup$
    – Nayuki
    Commented Jan 1, 2017 at 21:28
  • $\begingroup$ @TobiAlafin I think it's because semiconductor manufacturing revolves around single chips with a small number of logic layers. Only slowly are we starting to see more vertical stacking with technologies such as 3D NAND flash memories. $\endgroup$
    – Nayuki
    Commented Jan 1, 2017 at 21:28
  • 1
    $\begingroup$ @Raphael: I think this answer persuasively argues that some new kinds of physical computing devices can be modelled well by different (fine-grained) model of computational complexity. (A similar example would be going from a tape drives (modelled well by $O(n)$ memory access times) to SSDs (modelled well by $(\log n)$ access times, or if you squint, maybe $O(1)$).) $\endgroup$
    – j_random_hacker
    Commented Jan 11, 2017 at 15:21
1
$\begingroup$

As long as you stay in the realm of real, classical computation (i.e. a finite, discrete symbol set; finite control; finite memory): no. Real machines do not have any asymptotic nature so you can not speed them up asymptotically, either.

If you allow different theoretical computation models, the answer is trivially yes: different models imply different complexities for the same problem. Just compare TMs with RAMs.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.