<p>Purely functional programming is a popular abstraction that offers, at least according to its proponents, a great increase in the expressive power of code, among other benefits. However, since it is a restrictive model of the machine &mdash; in particular, not allowing mutable memory &mdash; it raises the question of asymptotic slowdown compared to the usual (RAM) model. </p>

<p>There's a great thread on this question <a href="https://stackoverflow.com/questions/1990464/efficiency-of-purely-functional-programming">here</a>. The main takeaways seem to be:</p>

<ol>
<li>You can simulate mutable memory with a balanced binary tree, so the worst case slowdown is O(log n).</li>
<li>With <em>eager evaluation</em>, there are problems for which this is the best you can do.</li>
<li>With <em>lazy evaluation</em>, it is not known whether or not there is a gap. However, there are many natural problems for which no known purely functional algorithms matches the optimal RAM complexity.</li>
</ol>

<p>It seems to me that this is a surprisingly basic question to be open.</p>

CC BY-SA 3.0
2012-12-14T09:21:48.530Z
For very large data computations, the IO cost should dominate so strongly that logarithmic slowdowns in the computations shouldn't matter, right?
adrianN
CC BY-SA 3.0
2017-09-16T14:31:22.650Z
What do you mean by the evaluation order?
libeako
CC BY-SA 3.0
2017-09-16T14:35:02.690Z
In the purely functional Haskell programming language one is able to modify elements of an array in an imperative style to achieve optimal asymptotic running time. See article "Lazy Functional State Threads".
libeako
CC BY-SA 2.5
2010-08-26T09:16:27.460Z
given that functional programming is a model for large data computations (see MapReduce), this slowdown is potentially quite significant.
Suresh Venkat
CC BY-SA 2.5
2010-08-26T14:44:26.360Z
Also, it's important to keep in mind that caveats mentioned in the SO thread.  Namely, the $\Omega(n \log n)$ lower bound on a problem is itself in an even more restricted model: online with atomic elements.  I believe a lower bound of that form in the standard model of functional programming is still open.
Joshua Grochow
CC BY-SA 2.5
2010-09-10T17:46:29.957Z
At least, the paper mentioned in that thread ([Bird, Jones and De Moor, 1997], see there for the full reference) establishes a gap betweeen eager and lazy evaluation.
Blaisorblade
CC BY-SA 2.5
2010-08-26T09:04:27.043Z
2010-09-10T17:47:21.247Z
2017-05-23T12:40:09.333Z
randomwalker
<p>Another beautiful example of the price of abstraction: <a href="http://en.wikipedia.org/wiki/Network_coding">network coding</a>. It's known that in multicast settings, the max-flow-min-cut relation is not one of equality (the primal and dual don't match). However, the traditional models assume flow that's merely passed on and not "processed" in any way. With network coding, you can beat this limit by cleverly combining flows. This example was a great motivator for the study of network coding in the first place. </p>

CC BY-SA 2.5
2010-08-26T08:43:22.763Z
2010-08-26T08:43:22.763Z
Suresh Venkat
<p>The "price of abstraction" can also be found when solving the discrete logarithm problem in cryptography. <a href="http://www.shoup.net/papers/dlbounds1.pdf">Shoup (1997)</a> has shown that any generic approach (i.e., algorithms using only group operations) has to use at least $\Omega(\sqrt{m})$ group operations, where $m$ is the size of the group. This matches the complexity of the generic <a href="http://en.wikipedia.org/wiki/Birthday_attack">birthday attack</a>. However, algorithms like the <a href="http://en.wikipedia.org/wiki/Index_calculus_algorithm">Index calculus</a> or the <a href="http://en.wikipedia.org/wiki/Pohlig-Hellman_algorithm">Pohlig-Hellman algorithm</a> rely on the number theoretic structure of $\mathbb{Z}_n^*$ to obtain slightly faster algorithms (at least in groups of smooth order).</p>

<p>This observation is one reason for the popularity of elliptic curve cryptography (as opposed to cryptography in groups such as $\mathbb{Z}_n^*$) since, essentially, we only know generic approaches to solve the discrete logarithm problem in groups based on elliptic curves.</p>

CC BY-SA 2.5
2010-08-26T11:51:58.473Z
2010-08-26T11:51:58.473Z
MRA
<p>While your question focuses on complexity theory, similar things can happen in other fields such as the theory of programming languages. Here are a couple of examples where abstraction makes something undecidable (i.e. the lower bound in the weak model is impossibility, while the strong model allows the algorithm to be expressed):</p>

<ul>
<li><p>In the lambda calculus, there are functions that you cannot express directly (i.e., as a lambda term that beta-reduces to the desired result). An example is parallel or (a function of two arguments that returns whichever one that terminates). Another example is a function that prints its argument literally (a function obviously cannot distinguish between two beta-equivalent arguments). The lack of expressiveness is due to enforcing the abstraction that beta-equivalent lambda-terms must be treated identically.</p></li>
<li><p>In a statically typed language that only has <a href="http://en.wikipedia.org/wiki/Parametric_polymorphism">parametric polymorphism</a>, such as ML with no fancy extension, it is impossible to write some functions — you get <a href="http://homepages.inf.ed.ac.uk/wadler/topics/parametricity.html#free">theorems for free</a>. For example, a function whose type is $\forall\alpha, \alpha\to\alpha$ (whatever the type of the argument is, return an object of the same type) must be either the identity function or non-terminating. The lack of expressiveness is due to the abstraction that if you don't know the type of a value, it's opaque (you can only pass it around).</p></li>
</ul>

CC BY-SA 2.5
2010-09-01T13:00:12.580Z
Wish I could up-vote this multiple times.
Jacques Carette
CC BY-SA 2.5
2010-08-26T22:48:07.880Z
2010-08-26T22:48:07.880Z
Gilles 'SO- stop being evil'
<p>Here's an example from graph algorithms. Given a directed graph with non-negative weights on the edges, the <strong>all-pairs bottleneck paths</strong> problem is to compute, for all pairs of vertices $s$ and $t$, the maximum flow that can be pushed along some path from $s$ to $t$. (Formally, we are just maximizing the minimum weight of an edge on any path from $s$ to $t$. More formally, we are replacing $\min$ and $+$ in the definition of all-pairs shortest paths with $\max$ and $\min$.)</p>

<p>Let $n$ be the number of vertices in the input graph. This problem was known to require $\Omega(n^3)$ time in the path-comparison model of  <a href="http://www.siam.org/cgi-bin/redirect/aip_redirect.pl?0222071">Karger, Koller, and Phillips</a>, just as the all-pairs shortest paths problem does. (The path-comparison model supports traditional algorithms, like Floyd-Warshall.) However, unlike all-pairs shortest paths, it turns out that all-pairs bottleneck paths can be solved in <a href="http://theoryofcomputing.org/articles/v005a009/">less than $O(n^{2.8})$ time</a> using fast matrix multiplication. </p>

CC BY-SA 2.5
2010-09-01T16:51:07.557Z
2010-09-01T16:51:07.557Z
Ryan Williams
<p>Per a discussion in <a href="https://cstheory.stackexchange.com/questions/2119/the-reasons-for-bss-real-ram-model-being-prefered-in-computational-geometry">this question</a>, many problems in computational geometry have $\Omega(n\log n)$ lower bounds in algebraic decision tree or algebraic computation tree models of computation, stemming from fundamental problems such as sorting or <a href="http://en.wikipedia.org/wiki/Element_distinctness_problem" rel="nofollow noreferrer">element distinctness</a>. It's not hard to find papers claiming that $O(n\log n)$ upper bounds on related problems such as the construction of Delaunay triangulations are optimal, because they match these lower bounds.</p>

<p>But when the input is specified in integer Cartesian coordinates (as it frequently is in practice, floating point being a bad fit for computational geometry), these lower bounds do not match the computational model. It's perhaps not surprising that orthogonal range search type problems can be solved faster using techniques adapted from integer sorting, but even non-orthogonal problems can often have faster algorithms (that solve the problem exactly, in models of computation allowing integer arithmetic with O(1) times the precision of the input integers). See e.g. <a href="http://arxiv.org/abs/1010.1948" rel="nofollow noreferrer">arXiv:1010.1948</a> for one set of examples.</p>

CC BY-SA 2.5
2010-10-13T07:01:13.167Z
Thanks for highlighting the "paradox", and the recent paper by Chan and Pǎtraşcu.
András Salamon
CC BY-SA 2.5
2010-10-12T20:42:14.130Z
2010-10-12T20:42:14.130Z
2017-04-13T12:32:28.080Z
David Eppstein
<p>There are many such examples in cryptography, especially zero-knowledge proofs. See e.g., the thesis:</p>

<p>Boaz Barak, Non-Black-Box Techniques in Cryptography, 2003.</p>

<p>(Incidentally, the thesis title provides a zero-knowledge proof of the validity of this comment :)</p>

CC BY-SA 2.5
2010-09-20T08:44:10.630Z
Please correct the citation year from 2006 to 2003.
Sadeq Dousti
CC BY-SA 2.5
2010-10-18T23:13:34.503Z
@Sadeq Dousti: done. It's community wiki and you have more reputation than me, so I guess you could have corrected that yourself ;-)
Blaisorblade
CC BY-SA 2.5
2010-08-26T04:44:56.560Z
2010-10-18T23:11:00.840Z
2010-10-18T23:11:00.840Z
Piotr
<p><a href="http://compgeom.cs.uiuc.edu/~jeffe/teaching/497/06-algebraic-tree.pdf">Algebraic Decision Trees</a> are used as a basis in computational geometry to show many simple problems like Element Uniqueness are $\Omega(n \log n)$.  These lower bounds are then used to show more complicated problems like Voronoi Diagrams also have $\Omega(n \log n)$ lower bounds.  I was then later surprised to read an $O(n)$ expected time algorithm for solving closest pair of points in the plane, which is a generalization of Element Uniqueness.  It escapes the Algebraic Decision Tree bound by using hashing.  I found it in the Algorithm Design book by Klein and Tardos.  There is a similar but more complicated algorithm for solving the same problem described on <a href="http://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin">R.J. Lipton's blog</a>.</p>

<p>Reference:  </p>

<ul>
<li>Richard J. Lipton, "<a href="http://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin">Rabin Flips a Coin</a>", March 2009<br>
published on <a href="http://rjlipton.wordpress.com/">Godel's Lost Letter and P=NP</a> blog.</li>
</ul>

CC BY-SA 3.0
2010-08-27T01:04:44.940Z
2012-12-13T04:29:21.260Z
2012-12-13T04:29:21.260Z
rrenaud
<p>Consider synchronous deterministic distributed algorithms for reducing the number of colours in a cycle graph from $k$ to $3$. That is, you are given a proper $k$-colouring of the cycle and you'd like to output a proper $3$-colouring of the cycle; each node of the cycle is a processor.</p>

<p>If you assume a comparison-based model (you treat the $k$ colours as black boxes that can be only transmitted from one node to another and compared to each other), you get a trivial lower bound of $\Omega(k)$ for the number of communication rounds.</p>

<p>However, this abstraction is arguably blatantly wrong: if you can transmit something in a communication network, you will have some way to encode "something" as a string of bits. And now things start to look much better.</p>

<p>If your colours aren't black boxes but integers $1, 2, ..., k$, then you can do the colour reduction by using Cole–Vishkin techniques in $O(\log^* k)$ communication rounds. Even if your colours are <em>huge</em> bit strings, like integers from $1, 2, ..., 10^{10^k}$, you'll get the same bound $O(\log^* k)$.</p>

<p>Bottom line: the price of the "wrong" abstraction: $O(\log^* k)$ vs. $\Omega(k)$ .</p>

CC BY-SA 2.5
2010-08-26T08:26:53.100Z
2010-08-26T08:26:53.100Z
Jukka Suomela
<p>An example that comes to my mind is computation of volume. A result by <a href="http://dx.doi.org/10.1007/BF02187886">Barany and Furedi</a> is that you need an exponential number of queries and there is a randomized polynomial time algorithm by <a href="http://doi.acm.org/10.1145/102782.102783">Dyer-Frieze-Kannan</a>. The gap represent the prize of abstraction and also the benefit of randomness but I think the main reason for the gap is the price of abstraction. (I hope I understood the question and it goes in the right direction.)</p>

CC BY-SA 2.5
2010-09-01T15:29:38.087Z
2010-09-01T16:37:28.820Z
2010-09-01T16:37:28.820Z
Gil Kalai
<p>Shannon-Nyquist sampling theorem proposes a sufficient condition for information theoretic bounds on communication. Sampling theory is worked around examples where the incoming signal has a compact/random representation. Recent advances in sampling show that this abstraction does perhaps comes with a price - that the sorts of things we are interested in measuring generally have <em>sparse</em> representations so that these bounds are not tight. Additionally, information can be encoded in a much denser way than originally thought.</p>

<ul>
<li>Error correcting codes suggest that some re-evaluation of the Shannon limit in networking landscapes subject to noise.</li>
<li>The brand new field of compressive sensing pushes reconstruction of the varieties of images we find interesting way beyond the Shannon limit.</li>
</ul>

CC BY-SA 3.0
2016-11-15T09:28:13.663Z
Can you give some references for this :)?
Vivek Bagaria
CC BY-SA 2.5
2010-09-01T08:37:46.073Z
2010-09-01T17:47:55.370Z
2010-09-01T17:47:55.370Z
Ross Snider
<p>Many interesting problems that nature sciences come up with turn out to be NP-hard in the classical sense. While this notion is theoretically perfectly valid it does not help the biologist or physicist in any way. We find that some NP-hard problems are <a href="http://en.wikipedia.org/wiki/Parameterized_complexity">fixed parameter treatable</a> and oftentimes with a parameter that is observed to be bounded by a small constant in the real world.</p>

<p>That is, TCS tells us that we do not expect an efficient solution for the abstract problem but we can solve actually occurring instances fast -- quite a gap.</p>

CC BY-SA 2.5
2010-11-04T09:08:01.347Z
2010-11-04T09:08:01.347Z
Raphael
<p>Reingold's algorithm solves undirected s-t connectivity in logarithmic space.</p>
<p>If we use a pointer machine, which maintains pointers as abstract objects without a total ordering, the problem can no longer be solved with a constant number of pointers. Paper &quot;Pointer Programs and Undirected Reachability&quot; by Schopp and Hofmann <a href="https://ulrichschoepp.de/Docs/reach.pdf" rel="noreferrer">https://ulrichschoepp.de/Docs/reach.pdf</a>.</p>

CC BY-SA 4.0
2022-11-05T20:33:19.533Z
Related: XOR linked lists are possible when pointers are integers and not abstract objects.
sdcvvc
CC BY-SA 4.0
2020-08-23T22:20:26.060Z
2020-08-23T22:20:26.060Z
sdcvvc
<p>This is probably not exactly what you had in mind. But in a certain sense, the independence of P vs NP from oracles is such an example. What it really says is that if all you care about is simulation and enumeration, (i.e if that's your "model" of computation), then you cannot separate these classes or collapse them.</p>

<p>A more concrete algorithmic example comes from approximate range searching in the "reverse" direction. Specifically, most range searching problems are phrased as semigroup sums, and lower/upper bounds are expressed without regard to the structure of this semigroup (except for some light technical conditions). Recent work by <a href="http://www.cs.umd.edu/~mount/Papers/stoc06-avd-integ.pdf">Arya, Malamatos and Mount</a> shows that if you look closely at the semigroup structure (the properties of idempotence and integrality), then you can prove different (and tighter) bounds for approximate range searching. </p>

CC BY-SA 2.5
2010-08-26T14:53:20.053Z
Although P vs NP is not what I had in mind, it's not *such* a bad example.  Incidentally, Arora, Impagliazzo, and Vazirani (http://cseweb.ucsd.edu/~russell/ias.ps) suggest that the key property that the general oracle model abstracts away is local checkability of computations.  In particular, if any oracle $X$ preserves local checkability and $P^X \neq NP^X$ then $P \neq NP$, and if $P^X = NP^X$ then $NP = coNP$.  Their work is somewhat controversial (I think it runs into issues of relativizing small-space bounded classes) but I think it's very interesting.
Joshua Grochow
CC BY-SA 2.5
2010-08-26T04:23:22.973Z
2010-08-26T04:23:22.973Z
Suresh Venkat
<p>In this paper <a href="http://www.mimuw.edu.pl/~szymtor/papers/atom-turing.pdf" rel="noreferrer">http://www.mimuw.edu.pl/~szymtor/papers/atom-turing.pdf</a>
we studied Turing Machines which have limited access to data.
This is formalized as being invariant under automorphisms of a relational structure; for instance, in the O(n log n) lower bound for sorting, you would say that the machine can processes and store rational numbers, but its transitions should be invariant under automorphisms of (Q,&lt;), i.e. monotone bijections. 
The formal definition is more complicated, in order to specify precisely what 
kind of data structures can the machine store in its memory (it should be "finite"<br>
in some sense, but we allow to store more complicated structures than only tuples of data values, such as unordered tuples).  </p>

<p>In the paper we proved some lower bounds for other Turing machines with "restricted data access". In particular, we showed that:</p>

<p>• A deterministic Turing machine which can handle vectors
(say over the two-element field), but can only use vector addition and equality tests, cannot determine in polynomial time whether a given list of vectors is linearly dependent (formally, the machines transitions should be invariant under automorphisms of the vector space). This is opposed to nondeterministic machines, which can simply guess a combination of the vectors which adds up to 0. Observe that Gaussian elimination runs in polynomial time, but has access to the coordinates of the vectors; in particular, its transitions are not invariant under automorphisms of the vector space.</p>

<p>• In a suitably defined model, Turing Machines which can compare
natural numbers only with respect to equality (not even &lt;) cannot be determinized.
Here, we consider the relational structure (N,=) and machines which are invariant under its automorphisms. 
There is a construction (similar to the Cai-Furer-Immerman construction from Finite Model Theory) which shows that in fact, in this model P≠NP. 
Allowing the machines to compare the numbers using &lt; gives them sufficient power to determinize. </p>

CC BY-SA 3.0
2013-09-04T13:40:06.150Z
2013-09-04T13:40:06.150Z
Szymon Toruńczyk
<p>When expressed in first order logic, any proof of the pigeonhole principle for fixed n is exponential in length. However, with arithmetic the proof can be expressed much more concisely. </p>

<p>The success of SMT solvers has come from backing off from the abstract model of reducing problems to SAT, allowing richer theories to greatly reduce the amount of computations needed.</p>

CC BY-SA 3.0
2016-06-22T23:15:43.973Z
2016-06-22T23:15:43.973Z
Arthur B
<p>A general price of abstraction is present in black-box frameworks like decision-tree complexity or quantum query complexity. If we restrict analysis to these models, then we can often find very good bounds on the complexity of tasks. In fact, for quantum query we can basically solve the complexity of problems because the negative adversary method provides tight lower bounds (within a factor of log n/loglog n: <a href="http://arxiv.org/abs/1005.1601" rel="nofollow">1005.1601</a>). This gives us a great tool for analyzing query complexity, but it often becomes difficult to compare the query complexity to more standard turing-machine time/space complexity (except as a crude lower bound).</p>

CC BY-SA 2.5
2010-10-22T17:08:00.083Z
Do you have some specific examples of where this has shown a lower bound that can be broken by "opening up the black box"?
Joshua Grochow
CC BY-SA 2.5
2010-10-22T17:30:40.233Z
well sorting is an example where the decision tree model gives you n log n, but you can get better by looking at the structure of the input.
Suresh Venkat
CC BY-SA 2.5
2010-10-22T17:41:46.327Z
@Suresh: I meant examples that haven't already been mentioned :).
Joshua Grochow
CC BY-SA 2.5
2010-10-22T18:05:50.880Z
sorry - my bad.
Suresh Venkat
CC BY-SA 2.5
2010-10-23T01:25:55.687Z
Well, sometimes you can have a relatively nice quantum query complexity but no fast running algorithm. An example is the hidden subgroup problem where we need a polynomial number of queries, but still an exponential time (although obviously the lower bound on time is not proven) for any known algorithm [1]. This is a price in the opposite direction, I guess.

[1] http://arxiv.org/abs/quant-ph/0401083
Artem Kaznatcheev
CC BY-SA 2.5
2010-10-22T15:55:05.737Z
2010-10-22T15:55:05.737Z
Artem Kaznatcheev
<p>Here are two examples, both related to continuous vs. discrete models:</p>
<ol>
<li>Suppose there is an (infinitesimally small) treasure hidden in the <span class="math-container">$[0,1]$</span> interval, in position <span class="math-container">$x$</span>. We want to find the treasure by digging. Whenever we dig in position <span class="math-container">$y$</span>, we get feedback of whether <span class="math-container">$x&lt;y$</span>, <span class="math-container">$x=y$</span> or <span class="math-container">$x&gt;y$</span>. Obviously, if <span class="math-container">$x$</span> can be any real number, then any search algorithm may never terminate. <span class="math-container">$|x-y|$</span> may be very small, but we might never arrive at <span class="math-container">$y=x$</span>.</li>
</ol>
<p>However, we can extend the search model to allow continuous sweeping. In this model, we just let <span class="math-container">$y$</span> run continuously over the <span class="math-container">$[0,1]$</span> interval, and get feedback whenever <span class="math-container">$y=x$</span>.</p>
<ol start="2">
<li>The motivation for problem A comes from the problem of <a href="http://en.wikipedia.org/wiki/Envy-free_division" rel="nofollow noreferrer">envy-free cake division</a>. <a href="https://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1r11" rel="nofollow noreferrer">Stromquist showed</a>, that no finite protocol (even if unbounded) can guarantee an envy-free division of a cake among three or more players, if each player is to receive a single connected piece.</li>
</ol>
<p>However, as <a href="https://link.springer.com/chapter/10.1007/978-3-642-17572-5_3" rel="nofollow noreferrer">Aumann and Dombb explained later</a>, this result applies only to a discrete cutting model, where &quot;In each step, the protocol selects a player <span class="math-container">$i$</span> and a real number <span class="math-container">$\alpha$</span>, and invites player <span class="math-container">$i$</span> to make a mark at the unique point <span class="math-container">$x$</span> for which <span class="math-container">$vi(0,x) = \alpha$</span>&quot;, &quot;and not for cases where, for example, some mediator has full information of the players’ valuation functions and proposes a division based on this information&quot;.</p>
<p>Additionally, the result does not relate to algorithms with continuous operations, such as moving-knife procedures.</p>

CC BY-SA 4.0
2013-04-12T13:56:56.997Z
2022-10-27T03:56:29.107Z
2022-10-27T03:56:29.107Z
Erel Segal-Halevi
<p>Theoretical computer science has provided some examples of &quot;the price of abstraction.&quot;  The two most prominent are for Gaussian elimination and sorting.  Namely:</p>
<ul>
<li>It is known that Gaussian elimination is optimal for, say, computing the determinant <em>if you restrict operations to rows and columns as a whole</em> <a href="https://www.sciencedirect.com/science/article/abs/pii/0041555365900650" rel="noreferrer">1</a>.  Obviously Strassen's algorithm does not obey that restriction, and it is asymptotically better than Gaussian elimination.</li>
<li>In sorting, if you treat the elements of the list as black boxes that can only be compared and moved around, then we have the standard <span class="math-container">$n \log n$</span> information-theoretic lower bound.  Yet fusion trees beat this bound by, as far as I understand it, clever use of multiplication.</li>
</ul>
<blockquote>
<p>Are there other examples of the price of abstraction?</p>
</blockquote>
<p>To be a bit more formal, I'm looking for examples where a lower bound is known unconditionally in some weak model of computation, but is known to be violated in a stronger model.  Furthermore, <em>the weakness of the weak model should come in the form of an abstraction</em>, which admittedly is a subjective notion.  For example, I do not consider the restriction to monotone circuits to be an abstraction.  Hopefully the two examples above make clear what I'm looking for.</p>
<p><a href="https://www.sciencedirect.com/science/article/abs/pii/0041555365900650" rel="noreferrer">1</a>  Klyuyev, V. V., and N. I. Kokovkin-Shcherbak: On the minimizations of the number of arithmetic operations for the solution of linear algebraic systems of equations. Translation by G. I. Tee: Technical Report CS 24, June 14, 1965, Computer Science Dept., Stanford University. <a href="https://www.sciencedirect.com/science/article/abs/pii/0041555365900650" rel="noreferrer">Available online.</a></p>

CC BY-SA 3.0
2012-10-01T17:16:12.053Z
seems like you might really be referring to [relaxation](http://en.wikipedia.org/wiki/Relaxation_technique_%28mathematics%29) instead of abstraction
vzn
CC BY-SA 2.5
2010-08-26T09:06:51.853Z
I really like this question; looking forward to seeing more answers.
randomwalker
CC BY-SA 2.5
2010-08-30T18:47:18.680Z
There's also an 'implicit' cost of abstraction. You mention the example of the price of abstraction in sorting, and how these abstracted results do not apply to the of sorting numbers (which can in fact be done in even O(n) with bucketsort in some cases). Lower bounds on Voronoi diagrams are often derived by showing that there is a linear time reduction from a Voronoi diagram to sorting a list of numbers. And many geometric algorithms derive lower bounds from this lower bound on computing the voronoi.
Ross Snider
CC BY-SA 2.5
2010-09-01T09:10:42.910Z
why is this a community wiki?
nanda
CC BY-SA 2.5
2010-09-01T19:41:42.117Z
@nanda: Because there's no single right answer, and in fact the question was designed to generate *many* right answers, as I think it has.
Joshua Grochow
<ds.algorithms><reference-request><big-list><lower-bounds>
Examples of the price of abstraction?
Joshua Grochow
# Examples of the price of abstraction?

(Asked by: username_0 on 2010-08-26)

Theoretical computer science has provided some examples of "the price of abstraction." The two most prominent are for Gaussian elimination and sorting. Namely:

* It is known that Gaussian elimination is optimal for, say, computing the determinant *if you restrict operations to rows and columns as a whole* [1](https://www.sciencedirect.com/science/article/abs/pii/0041555365900650). Obviously Strassen's algorithm does not obey that restriction, and it is asymptotically better than Gaussian elimination.
* In sorting, if you treat the elements of the list as black boxes that can only be compared and moved around, then we have the standard $n \log n$ information-theoretic lower bound. Yet fusion trees beat this bound by, as far as I understand it, clever use of multiplication.

> Are there other examples of the price of abstraction?

To be a bit more formal, I'm looking for examples where a lower bound is known unconditionally in some weak model of computation, but is known to be violated in a stronger model. Furthermore, *the weakness of the weak model should come in the form of an abstraction*, which admittedly is a subjective notion. For example, I do not consider the restriction to monotone circuits to be an abstraction. Hopefully the two examples above make clear what I'm looking for.

[1](https://www.sciencedirect.com/science/article/abs/pii/0041555365900650) Klyuyev, V. V., and N. I. Kokovkin-Shcherbak: On the minimizations of the number of arithmetic operations for the solution of linear algebraic systems of equations. Translation by G. I. Tee: Technical Report CS 24, June 14, 1965, Computer Science Dept., Stanford University. [Available online.](https://www.sciencedirect.com/science/article/abs/pii/0041555365900650)

**Tags:** ds.algorithms, reference-request, big-list, lower-bounds
> **Comments:**
> **username_2**: I really like this question; looking forward to seeing more answers.  
> **username_3**: There's also an 'implicit' cost of abstraction. You mention the example of the price of abstraction in sorting, and how these abstracted results do not apply to the of sorting numbers (which can in fact be done in even O(n) with bucketsort in some cases). Lower bounds on Voronoi diagrams are often derived by showing that there is a linear time reduction from a Voronoi diagram to sorting a list of numbers. And many geometric algorithms derive lower bounds from this lower bound on computing the voronoi.  
> **username_4**: why is this a community wiki?  
> **username_0**: @nanda: Because there's no single right answer, and in fact the question was designed to generate *many* right answers, as I think it has.  
> **username_1**: seems like you might really be referring to [relaxation](http://en.wikipedia.org/wiki/Relaxation_technique_%28mathematics%29) instead of abstraction  

---

## 18 answers

### Answer by username_2 on 2010-08-26. Score: 44

Purely functional programming is a popular abstraction that offers, at least according to its proponents, a great increase in the expressive power of code, among other benefits. However, since it is a restrictive model of the machine — in particular, not allowing mutable memory — it raises the question of asymptotic slowdown compared to the usual (RAM) model.

There's a great thread on this question [here](https://stackoverflow.com/questions/1990464/efficiency-of-purely-functional-programming). The main takeaways seem to be:

1. You can simulate mutable memory with a balanced binary tree, so the worst case slowdown is O(log n).
2. With *eager evaluation*, there are problems for which this is the best you can do.
3. With *lazy evaluation*, it is not known whether or not there is a gap. However, there are many natural problems for which no known purely functional algorithms matches the optimal RAM complexity.

It seems to me that this is a surprisingly basic question to be open.

> **Comments:**
> **username_7**: given that functional programming is a model for large data computations (see MapReduce), this slowdown is potentially quite significant.  
> **username_0**: Also, it's important to keep in mind that caveats mentioned in the SO thread.  Namely, the $\Omega(n \log n)$ lower bound on a problem is itself in an even more restricted model: online with atomic elements.  I believe a lower bound of that form in the standard model of functional programming is still open.  
> **username_8**: At least, the paper mentioned in that thread ([Bird, Jones and De Moor, 1997], see there for the full reference) establishes a gap betweeen eager and lazy evaluation.  
> **username_5**: For very large data computations, the IO cost should dominate so strongly that logarithmic slowdowns in the computations shouldn't matter, right?  
> **username_6**: What do you mean by the evaluation order?  
> **username_6**: In the purely functional Haskell programming language one is able to modify elements of an array in an imperative style to achieve optimal asymptotic running time. See article "Lazy Functional State Threads".  

---

### Answer by username_7 on 2010-08-26. Score: 43

Another beautiful example of the price of abstraction: [network coding](http://en.wikipedia.org/wiki/Network_coding). It's known that in multicast settings, the max-flow-min-cut relation is not one of equality (the primal and dual don't match). However, the traditional models assume flow that's merely passed on and not "processed" in any way. With network coding, you can beat this limit by cleverly combining flows. This example was a great motivator for the study of network coding in the first place.


---

### Answer by username_9 on 2010-08-26. Score: 31

The "price of abstraction" can also be found when solving the discrete logarithm problem in cryptography. [Shoup (1997)](http://www.shoup.net/papers/dlbounds1.pdf) has shown that any generic approach (i.e., algorithms using only group operations) has to use at least $\Omega(\sqrt{m})$ group operations, where $m$ is the size of the group. This matches the complexity of the generic [birthday attack](http://en.wikipedia.org/wiki/Birthday_attack). However, algorithms like the [Index calculus](http://en.wikipedia.org/wiki/Index_calculus_algorithm) or the [Pohlig-Hellman algorithm](http://en.wikipedia.org/wiki/Pohlig-Hellman_algorithm) rely on the number theoretic structure of $\mathbb{Z}\_n^\*$ to obtain slightly faster algorithms (at least in groups of smooth order).

This observation is one reason for the popularity of elliptic curve cryptography (as opposed to cryptography in groups such as $\mathbb{Z}\_n^\*$) since, essentially, we only know generic approaches to solve the discrete logarithm problem in groups based on elliptic curves.


---

### Answer by username_10 on 2010-08-26. Score: 31

While your question focuses on complexity theory, similar things can happen in other fields such as the theory of programming languages. Here are a couple of examples where abstraction makes something undecidable (i.e. the lower bound in the weak model is impossibility, while the strong model allows the algorithm to be expressed):

* In the lambda calculus, there are functions that you cannot express directly (i.e., as a lambda term that beta-reduces to the desired result). An example is parallel or (a function of two arguments that returns whichever one that terminates). Another example is a function that prints its argument literally (a function obviously cannot distinguish between two beta-equivalent arguments). The lack of expressiveness is due to enforcing the abstraction that beta-equivalent lambda-terms must be treated identically.
* In a statically typed language that only has [parametric polymorphism](http://en.wikipedia.org/wiki/Parametric_polymorphism), such as ML with no fancy extension, it is impossible to write some functions — you get [theorems for free](http://homepages.inf.ed.ac.uk/wadler/topics/parametricity.html#free). For example, a function whose type is $\forall\alpha, \alpha\to\alpha$ (whatever the type of the argument is, return an object of the same type) must be either the identity function or non-terminating. The lack of expressiveness is due to the abstraction that if you don't know the type of a value, it's opaque (you can only pass it around).

> **Comments:**
> **username_11**: Wish I could up-vote this multiple times.  

---

### Answer by username_12 on 2010-09-01. Score: 30

Here's an example from graph algorithms. Given a directed graph with non-negative weights on the edges, the **all-pairs bottleneck paths** problem is to compute, for all pairs of vertices $s$ and $t$, the maximum flow that can be pushed along some path from $s$ to $t$. (Formally, we are just maximizing the minimum weight of an edge on any path from $s$ to $t$. More formally, we are replacing $\min$ and $+$ in the definition of all-pairs shortest paths with $\max$ and $\min$.)

Let $n$ be the number of vertices in the input graph. This problem was known to require $\Omega(n^3)$ time in the path-comparison model of [Karger, Koller, and Phillips](http://www.siam.org/cgi-bin/redirect/aip_redirect.pl?0222071), just as the all-pairs shortest paths problem does. (The path-comparison model supports traditional algorithms, like Floyd-Warshall.) However, unlike all-pairs shortest paths, it turns out that all-pairs bottleneck paths can be solved in [less than $O(n^{2.8})$ time](http://theoryofcomputing.org/articles/v005a009/) using fast matrix multiplication.


---

### Answer by username_13 on 2010-10-12. Score: 23

Per a discussion in [this question](https://cstheory.stackexchange.com/questions/2119/the-reasons-for-bss-real-ram-model-being-prefered-in-computational-geometry), many problems in computational geometry have $\Omega(n\log n)$ lower bounds in algebraic decision tree or algebraic computation tree models of computation, stemming from fundamental problems such as sorting or [element distinctness](http://en.wikipedia.org/wiki/Element_distinctness_problem). It's not hard to find papers claiming that $O(n\log n)$ upper bounds on related problems such as the construction of Delaunay triangulations are optimal, because they match these lower bounds.

But when the input is specified in integer Cartesian coordinates (as it frequently is in practice, floating point being a bad fit for computational geometry), these lower bounds do not match the computational model. It's perhaps not surprising that orthogonal range search type problems can be solved faster using techniques adapted from integer sorting, but even non-orthogonal problems can often have faster algorithms (that solve the problem exactly, in models of computation allowing integer arithmetic with O(1) times the precision of the input integers). See e.g. [arXiv:1010.1948](http://arxiv.org/abs/1010.1948) for one set of examples.

> **Comments:**
> **username_14**: Thanks for highlighting the "paradox", and the recent paper by Chan and Pǎtraşcu.  

---

### Answer by username_15 on 2010-08-26. Score: 21

There are many such examples in cryptography, especially zero-knowledge proofs. See e.g., the thesis:

Boaz Barak, Non-Black-Box Techniques in Cryptography, 2003.

(Incidentally, the thesis title provides a zero-knowledge proof of the validity of this comment :)

> **Comments:**
> **username_16**: Please correct the citation year from 2006 to 2003.  
> **username_8**: @Sadeq Dousti: done. It's community wiki and you have more reputation than me, so I guess you could have corrected that yourself ;-)  

---

### Answer by username_17 on 2010-08-27. Score: 20

[Algebraic Decision Trees](http://compgeom.cs.uiuc.edu/~jeffe/teaching/497/06-algebraic-tree.pdf) are used as a basis in computational geometry to show many simple problems like Element Uniqueness are $\Omega(n \log n)$. These lower bounds are then used to show more complicated problems like Voronoi Diagrams also have $\Omega(n \log n)$ lower bounds. I was then later surprised to read an $O(n)$ expected time algorithm for solving closest pair of points in the plane, which is a generalization of Element Uniqueness. It escapes the Algebraic Decision Tree bound by using hashing. I found it in the Algorithm Design book by Klein and Tardos. There is a similar but more complicated algorithm for solving the same problem described on [R.J. Lipton's blog](http://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin).

Reference:

* Richard J. Lipton, "[Rabin Flips a Coin](http://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin)", March 2009  
  published on [Godel's Lost Letter and P=NP](http://rjlipton.wordpress.com/) blog.


---

### Answer by username_18 on 2010-08-26. Score: 17

Consider synchronous deterministic distributed algorithms for reducing the number of colours in a cycle graph from $k$ to $3$. That is, you are given a proper $k$-colouring of the cycle and you'd like to output a proper $3$-colouring of the cycle; each node of the cycle is a processor.

If you assume a comparison-based model (you treat the $k$ colours as black boxes that can be only transmitted from one node to another and compared to each other), you get a trivial lower bound of $\Omega(k)$ for the number of communication rounds.

However, this abstraction is arguably blatantly wrong: if you can transmit something in a communication network, you will have some way to encode "something" as a string of bits. And now things start to look much better.

If your colours aren't black boxes but integers $1, 2, ..., k$, then you can do the colour reduction by using Cole–Vishkin techniques in $O(\log^\* k)$ communication rounds. Even if your colours are *huge* bit strings, like integers from $1, 2, ..., 10^{10^k}$, you'll get the same bound $O(\log^\* k)$.

Bottom line: the price of the "wrong" abstraction: $O(\log^\* k)$ vs. $\Omega(k)$ .


---

### Answer by username_19 on 2010-09-01. Score: 14

An example that comes to my mind is computation of volume. A result by [Barany and Furedi](http://dx.doi.org/10.1007/BF02187886) is that you need an exponential number of queries and there is a randomized polynomial time algorithm by [Dyer-Frieze-Kannan](http://doi.acm.org/10.1145/102782.102783). The gap represent the prize of abstraction and also the benefit of randomness but I think the main reason for the gap is the price of abstraction. (I hope I understood the question and it goes in the right direction.)


---

### Answer by username_3 on 2010-09-01. Score: 13

Shannon-Nyquist sampling theorem proposes a sufficient condition for information theoretic bounds on communication. Sampling theory is worked around examples where the incoming signal has a compact/random representation. Recent advances in sampling show that this abstraction does perhaps comes with a price - that the sorts of things we are interested in measuring generally have *sparse* representations so that these bounds are not tight. Additionally, information can be encoded in a much denser way than originally thought.

* Error correcting codes suggest that some re-evaluation of the Shannon limit in networking landscapes subject to noise.
* The brand new field of compressive sensing pushes reconstruction of the varieties of images we find interesting way beyond the Shannon limit.

> **Comments:**
> **username_20**: Can you give some references for this :)?  

---

### Answer by username_7 on 2010-08-26. Score: 10

This is probably not exactly what you had in mind. But in a certain sense, the independence of P vs NP from oracles is such an example. What it really says is that if all you care about is simulation and enumeration, (i.e if that's your "model" of computation), then you cannot separate these classes or collapse them.

A more concrete algorithmic example comes from approximate range searching in the "reverse" direction. Specifically, most range searching problems are phrased as semigroup sums, and lower/upper bounds are expressed without regard to the structure of this semigroup (except for some light technical conditions). Recent work by [Arya, Malamatos and Mount](http://www.cs.umd.edu/~mount/Papers/stoc06-avd-integ.pdf) shows that if you look closely at the semigroup structure (the properties of idempotence and integrality), then you can prove different (and tighter) bounds for approximate range searching.

> **Comments:**
> **username_0**: Although P vs NP is not what I had in mind, it's not *such* a bad example.  Incidentally, Arora, Impagliazzo, and Vazirani (http://cseweb.ucsd.edu/~russell/ias.ps) suggest that the key property that the general oracle model abstracts away is local checkability of computations.  In particular, if any oracle $X$ preserves local checkability and $P^X \neq NP^X$ then $P \neq NP$, and if $P^X = NP^X$ then $NP = coNP$.  Their work is somewhat controversial (I think it runs into issues of relativizing small-space bounded classes) but I think it's very interesting.  

---

### Answer by username_21 on 2010-11-04. Score: 9

Many interesting problems that nature sciences come up with turn out to be NP-hard in the classical sense. While this notion is theoretically perfectly valid it does not help the biologist or physicist in any way. We find that some NP-hard problems are [fixed parameter treatable](http://en.wikipedia.org/wiki/Parameterized_complexity) and oftentimes with a parameter that is observed to be bounded by a small constant in the real world.

That is, TCS tells us that we do not expect an efficient solution for the abstract problem but we can solve actually occurring instances fast -- quite a gap.


---

### Answer by username_22 on 2020-08-23. Score: 8

Reingold's algorithm solves undirected s-t connectivity in logarithmic space.

If we use a pointer machine, which maintains pointers as abstract objects without a total ordering, the problem can no longer be solved with a constant number of pointers. Paper "Pointer Programs and Undirected Reachability" by Schopp and Hofmann <https://ulrichschoepp.de/Docs/reach.pdf>.

> **Comments:**
> **username_22**: Related: XOR linked lists are possible when pointers are integers and not abstract objects.  

---

### Answer by username_23 on 2013-09-04. Score: 6

In this paper <http://www.mimuw.edu.pl/~szymtor/papers/atom-turing.pdf>
we studied Turing Machines which have limited access to data.
This is formalized as being invariant under automorphisms of a relational structure; for instance, in the O(n log n) lower bound for sorting, you would say that the machine can processes and store rational numbers, but its transitions should be invariant under automorphisms of (Q,<), i.e. monotone bijections.
The formal definition is more complicated, in order to specify precisely what
kind of data structures can the machine store in its memory (it should be "finite"  
in some sense, but we allow to store more complicated structures than only tuples of data values, such as unordered tuples).

In the paper we proved some lower bounds for other Turing machines with "restricted data access". In particular, we showed that:

• A deterministic Turing machine which can handle vectors
(say over the two-element field), but can only use vector addition and equality tests, cannot determine in polynomial time whether a given list of vectors is linearly dependent (formally, the machines transitions should be invariant under automorphisms of the vector space). This is opposed to nondeterministic machines, which can simply guess a combination of the vectors which adds up to 0. Observe that Gaussian elimination runs in polynomial time, but has access to the coordinates of the vectors; in particular, its transitions are not invariant under automorphisms of the vector space.

• In a suitably defined model, Turing Machines which can compare
natural numbers only with respect to equality (not even <) cannot be determinized.
Here, we consider the relational structure (N,=) and machines which are invariant under its automorphisms.
There is a construction (similar to the Cai-Furer-Immerman construction from Finite Model Theory) which shows that in fact, in this model P≠NP.
Allowing the machines to compare the numbers using < gives them sufficient power to determinize.


---

### Answer by username_24 on 2016-06-22. Score: 4

When expressed in first order logic, any proof of the pigeonhole principle for fixed n is exponential in length. However, with arithmetic the proof can be expressed much more concisely.

The success of SMT solvers has come from backing off from the abstract model of reducing problems to SAT, allowing richer theories to greatly reduce the amount of computations needed.


---

### Answer by username_25 on 2010-10-22. Score: 2

A general price of abstraction is present in black-box frameworks like decision-tree complexity or quantum query complexity. If we restrict analysis to these models, then we can often find very good bounds on the complexity of tasks. In fact, for quantum query we can basically solve the complexity of problems because the negative adversary method provides tight lower bounds (within a factor of log n/loglog n: [1005.1601](http://arxiv.org/abs/1005.1601)). This gives us a great tool for analyzing query complexity, but it often becomes difficult to compare the query complexity to more standard turing-machine time/space complexity (except as a crude lower bound).

> **Comments:**
> **username_0**: Do you have some specific examples of where this has shown a lower bound that can be broken by "opening up the black box"?  
> **username_7**: well sorting is an example where the decision tree model gives you n log n, but you can get better by looking at the structure of the input.  
> **username_0**: @Suresh: I meant examples that haven't already been mentioned :).  
> **username_7**: sorry - my bad.  
> **username_25**: Well, sometimes you can have a relatively nice quantum query complexity but no fast running algorithm. An example is the hidden subgroup problem where we need a polynomial number of queries, but still an exponential time (although obviously the lower bound on time is not proven) for any known algorithm [1]. This is a price in the opposite direction, I guess.  [1] http://arxiv.org/abs/quant-ph/0401083  

---

### Answer by username_26 on 2013-04-12. Score: 1

Here are two examples, both related to continuous vs. discrete models:

1. Suppose there is an (infinitesimally small) treasure hidden in the $[0,1]$ interval, in position $x$. We want to find the treasure by digging. Whenever we dig in position $y$, we get feedback of whether $x, $x=y$ or $x>y$. Obviously, if $x$ can be any real number, then any search algorithm may never terminate. $|x-y|$ may be very small, but we might never arrive at $y=x$.

However, we can extend the search model to allow continuous sweeping. In this model, we just let $y$ run continuously over the $[0,1]$ interval, and get feedback whenever $y=x$.

2. The motivation for problem A comes from the problem of [envy-free cake division](http://en.wikipedia.org/wiki/Envy-free_division). [Stromquist showed](https://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1r11), that no finite protocol (even if unbounded) can guarantee an envy-free division of a cake among three or more players, if each player is to receive a single connected piece.

However, as [Aumann and Dombb explained later](https://link.springer.com/chapter/10.1007/978-3-642-17572-5_3), this result applies only to a discrete cutting model, where "In each step, the protocol selects a player $i$ and a real number $\alpha$, and invites player $i$ to make a mark at the unique point $x$ for which $vi(0,x) = \alpha$", "and not for cases where, for example, some mediator has full information of the players’ valuation functions and proposes a division based on this information".

Additionally, the result does not relate to algorithms with continuous operations, such as moving-knife procedures.


---

