There are many examples where someone replaces a CPU with a GPU or an FPGA and get a performance boost of $\times 100$ or more, but is it possible for a change in the architecture of computational resource to reduce the least possible complexity of solving a problem, say, from $\Theta(n^2)$ to $\Theta(n)$?

Basically, I'm looking for an example like Bead sort.

| cite | improve this question | | | | |
  • $\begingroup$ It depends on how you define complexity. If you use PRAMs instead of a Turing Machine, then you can sort a list of $n$ elements in time $\mathcal{O}(\log n)$, however the total number of operations performed accross all processors is still $\mathcal{O}(n\cdot \log n)$. Then you can also consider quantum circuits: but I'm not sure how to quantify the complexity of quantum gates vs classical gates. $\endgroup$ – eru-cs Dec 14 '19 at 11:10
  • $\begingroup$ In the quantum setting, Grover's algorithm searches unstructured databases in time $\sqrt{n}$ vs $n$ on a classical Turing Machine. $\endgroup$ – eru-cs Dec 14 '19 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.