<p>This is a followup to Suresh's answer.  As he says, there are <em>lots</em> of construction problems in computational geometry where the complexity of the output is a trivial lower bound on the running time of any algorithm.  For example: planar line arrangements, 3-dimensional Voronoi diagrams, and planar visibility graphs all have combinatorial complexity $\Theta(n^2)$ in the worst case, so any algorithm that constructs those objects trivially requires $\Omega(n^2)$ time in the worst case.  (There are $O(n^2)$-time algorithms for all three of those problems.)</p>

<p>But similar constraints are conjectured to apply to <em>decision</em> problems as well.  For example, given a set of n lines in the plane, how easily can you check whether any three lines pass through a common point?  Well, you could build the arrangement of the lines (the planar graph defined by their intersection points and the segments between them), but that takes $\Theta(n^2)$ time.  One of the main results of <a href="http://www.cs.uiuc.edu/~jeffe/pubs/thesis.html">my PhD thesis</a> was that within a restricted but natural decision tree model of computation, <a href="http://www.cs.uiuc.edu/~jeffe/pubs/degen.html">$\Omega(n^2)$ time is required</a> to detect triple intersections.  Intuitively, we <em>must</em> enumerate all $\binom{n}{2}$ intersection points and look for duplicates.</p>

<p>Similarly, there is a set of numbers where $\Theta(n^2)$ triples of elements sum to zero.  Therefore, any algorithm (modeled by a certain class of decision trees) to test whether a given set contains three elements that sum to zero <a href="http://portal.acm.org/citation.cfm?id=1059515">requires $\Omega(n^2)$ time</a>.  (It's possible to <a href="http://erikdemaine.org/papers/3SUM_Algorithmica/">shave off some logs</a> via bit-level parallelism, but whatever.)</p>

<p>Another example, also from my thesis, is Hopcroft's problem: Given $n$ points and $n$ lines in the plane, does any point contain any line.  The worst-case number of point-line incidences is known to be $\Theta(n^{4/3})$.  I proved that in a restricted (but still natural) model of computation, <a href="http://www.cs.uiuc.edu/~jeffe/pubs/thesis.html">$\Omega(n^{4/3})$ time is required</a> to determine whether there is even one point-line incidence.  Intuitively, we must enumerate all $\Theta(n^{4/3})$ <em>near</em>-incidences and check each one to see whether it's really an incidence.</p>

<p>Formally, these lower bounds are still just conjectures, because they require restricted models of computation, which are specialized to the problem at hand, especially for Hopcroft's problem).  However, proving lower bounds for these problems in the RAM model is likely just as hard as any other lower-bound problem (ie, we have no clue) — see the <a href="http://people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf">SODA 2010 paper by Patrascu and Williams</a> relating generalizations of 3SUM to the exponential time hypothesis.</p>

CC BY-SA 2.5
2011-03-31T05:20:49.930Z
2011-03-31T05:20:49.930Z
Jeffε
<p>I am not completely sure if this is what you mean but there are a bunch of problems which don't seem like they are counting problems, however, the best ways that we know how to solve them is to count objects. One such problem is detecting whether a graph contains a triangle. The fastest known algorithm is to compute the trace of the cube of the adjacency matrix, which is 6 times the number of triangles in the (undirected) graph. This takes O($|V|^{2.376}$) time using the Coppersmith-Winograd matrix multiplication algorithm, and was first noticed by <a href="http://www.cs.technion.ac.il/~itai/publications/Algorithms/min-circuit.pdf">Itai and Rodeh</a> in 1978. Similarly, the best way we know to detect a k-clique is to find the number of k-cliques, again via matrix multiplication.</p>

CC BY-SA 2.5
2011-03-31T22:12:50.083Z
2011-03-31T22:12:50.083Z
virgi
<p>Valiant proved that the problem of finding the permanent of a matrix is complete for <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aSymbols#sharpp" rel="nofollow">#P</a>. See the <a href="http://en.wikipedia.org/wiki/Permanent_is_sharp-P-complete" rel="nofollow">wikipedia page</a> on the issue. #P is the complexity class corresponding to counting the number of accepting paths of an NP machine.</p>

CC BY-SA 2.5
2011-03-30T17:48:27.683Z
2011-03-30T17:48:27.683Z
Joe Fitzsimons
<p>Bipartite Planar (and log genus) Perfect Matching is a problem where Kastelyn's algorithm for counting planar matchings (extended by Galluccio and Loebl and
parallelized by Kulkarni, Mahajan &amp; Vardarajan) plays an important role even in
the search version of the problem. All relevant references can be found in the following paper:</p>

<p>Some perfect matchings and perfect half-integral matchings in NC.
Raghav Kulkarni, Meena Mahajan and Kasturi R. Varadarajan.
Chicago Journal of Theoretical Computer Science , Volume 2008 Article 4. </p>

CC BY-SA 3.0
2011-07-16T20:57:06.677Z
2011-07-16T20:57:06.677Z
SamiD
<p>I'll take "greatly influenced" as a soft constraint rather than as a reduction. In that sense, MANY problems in computational geometry have running times that are bounded by some combinatorial structure underlying them. for example, the complexity of computing an arrangement of shapes is directly linked to the intrinsic complexity of such arrangements. </p>

<p>Another, topical example of this is that various problems in point pattern matching have running times that boil down to estimating quantities like the number of repeated distances in a point set, and so on. </p>

CC BY-SA 2.5
2011-03-30T19:22:59.207Z
2011-03-30T19:22:59.207Z
Suresh Venkat
<p>Not sure if this is what you were looking for but phase transitions of NP-Complete problems rely heavily on probabilistic arguments, which are just another form of counting.</p>

<p><a href="http://www.google.com/url?sa=t&amp;source=web&amp;cd=4&amp;ved=0CDEQFjAD&amp;url=http%3A%2F%2Fwww.farcaster.com%2Fpapers%2Fcrypto-sumcc%2Fsumcc.ps&amp;rct=j&amp;q=subset%20sum%20crypto%20lattice%20reduction&amp;ei=N5uTTdvUMM-3tgf6_tBm&amp;usg=AFQjCNFcHqW4nF8N0T2dRYacBrTsWRGJuQ&amp;cad=rja" rel="nofollow">LLL</a> has been used to solve some 'low-density' Subset Sum problems, the success of which relies on high probability short lattice vectors existing that meet the criteria of being a Subset Sum solution.  <a href="http://arxiv.org/PS_cache/cs/pdf/0212/0212002v4.pdf" rel="nofollow">Survey Propagation</a> relies on the structure of solution space (and the number of solutions as it fixes variables) to find solutions near the critical threshold.</p>

<p><a href="http://research.microsoft.com/en-us/um/people/jchayes/Papers/partitionSTOC.pdf" rel="nofollow">Borgs, Chayes and Pittel</a> have pretty much completely characterized the phase transition of the (Uniform) Random Number Partition Problem and thus have characterized how many solutions one can expect for a given (random) instance of the Number Partition Problem.</p>

CC BY-SA 2.5
2011-03-30T21:19:23.977Z
2011-03-30T21:19:23.977Z
user834
<p>What I refer to as counting is the problem that consists in finding
the number of solutions to a function. More precisely, given a
function $f:N\to \{0,1\}$ (not necessarily black-box), approximate
$\#\{x\in N\mid f(x)= 1\}= |f^{-1}(1)|$.</p>

<p>I am looking for algorithmic problems which involve some sort of
counting and for which the time complexity is greatly influenced by
this underlying counting problem. </p>

<p>Of course, I am looking for problems which are not counting problems themselves. And it would be greatly appreciated if you could provide documentation for these problems.</p>

<ds.algorithms><reference-request><counting-complexity><time-complexity>
Any algorithmic problem has a time complexity dominated by counting?
lamontap
# Any algorithmic problem has a time complexity dominated by counting?

(Asked by: username_0 on 2011-03-30)

What I refer to as counting is the problem that consists in finding
the number of solutions to a function. More precisely, given a
function $f:N\to \{0,1\}$ (not necessarily black-box), approximate
$\#\{x\in N\mid f(x)= 1\}= |f^{-1}(1)|$.

I am looking for algorithmic problems which involve some sort of
counting and for which the time complexity is greatly influenced by
this underlying counting problem.

Of course, I am looking for problems which are not counting problems themselves. And it would be greatly appreciated if you could provide documentation for these problems.

**Tags:** ds.algorithms, reference-request, counting-complexity, time-complexity

---

## 6 answers

### Answer by username_1 on 2011-03-31. Score: 15

This is a followup to Suresh's answer. As he says, there are *lots* of construction problems in computational geometry where the complexity of the output is a trivial lower bound on the running time of any algorithm. For example: planar line arrangements, 3-dimensional Voronoi diagrams, and planar visibility graphs all have combinatorial complexity $\Theta(n^2)$ in the worst case, so any algorithm that constructs those objects trivially requires $\Omega(n^2)$ time in the worst case. (There are $O(n^2)$-time algorithms for all three of those problems.)

But similar constraints are conjectured to apply to *decision* problems as well. For example, given a set of n lines in the plane, how easily can you check whether any three lines pass through a common point? Well, you could build the arrangement of the lines (the planar graph defined by their intersection points and the segments between them), but that takes $\Theta(n^2)$ time. One of the main results of [my PhD thesis](http://www.cs.uiuc.edu/~jeffe/pubs/thesis.html) was that within a restricted but natural decision tree model of computation, [$\Omega(n^2)$ time is required](http://www.cs.uiuc.edu/~jeffe/pubs/degen.html) to detect triple intersections. Intuitively, we *must* enumerate all $\binom{n}{2}$ intersection points and look for duplicates.

Similarly, there is a set of numbers where $\Theta(n^2)$ triples of elements sum to zero. Therefore, any algorithm (modeled by a certain class of decision trees) to test whether a given set contains three elements that sum to zero [requires $\Omega(n^2)$ time](http://portal.acm.org/citation.cfm?id=1059515). (It's possible to [shave off some logs](http://erikdemaine.org/papers/3SUM_Algorithmica/) via bit-level parallelism, but whatever.)

Another example, also from my thesis, is Hopcroft's problem: Given $n$ points and $n$ lines in the plane, does any point contain any line. The worst-case number of point-line incidences is known to be $\Theta(n^{4/3})$. I proved that in a restricted (but still natural) model of computation, [$\Omega(n^{4/3})$ time is required](http://www.cs.uiuc.edu/~jeffe/pubs/thesis.html) to determine whether there is even one point-line incidence. Intuitively, we must enumerate all $\Theta(n^{4/3})$ *near*-incidences and check each one to see whether it's really an incidence.

Formally, these lower bounds are still just conjectures, because they require restricted models of computation, which are specialized to the problem at hand, especially for Hopcroft's problem). However, proving lower bounds for these problems in the RAM model is likely just as hard as any other lower-bound problem (ie, we have no clue) — see the [SODA 2010 paper by Patrascu and Williams](http://people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf) relating generalizations of 3SUM to the exponential time hypothesis.


---

### Answer by username_2 on 2011-03-31. Score: 9

I am not completely sure if this is what you mean but there are a bunch of problems which don't seem like they are counting problems, however, the best ways that we know how to solve them is to count objects. One such problem is detecting whether a graph contains a triangle. The fastest known algorithm is to compute the trace of the cube of the adjacency matrix, which is 6 times the number of triangles in the (undirected) graph. This takes O($|V|^{2.376}$) time using the Coppersmith-Winograd matrix multiplication algorithm, and was first noticed by [Itai and Rodeh](http://www.cs.technion.ac.il/~itai/publications/Algorithms/min-circuit.pdf) in 1978. Similarly, the best way we know to detect a k-clique is to find the number of k-cliques, again via matrix multiplication.


---

### Answer by username_3 on 2011-03-30. Score: 8

Valiant proved that the problem of finding the permanent of a matrix is complete for [#P](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aSymbols#sharpp). See the [wikipedia page](http://en.wikipedia.org/wiki/Permanent_is_sharp-P-complete) on the issue. #P is the complexity class corresponding to counting the number of accepting paths of an NP machine.


---

### Answer by username_4 on 2011-07-16. Score: 3

Bipartite Planar (and log genus) Perfect Matching is a problem where Kastelyn's algorithm for counting planar matchings (extended by Galluccio and Loebl and
parallelized by Kulkarni, Mahajan & Vardarajan) plays an important role even in
the search version of the problem. All relevant references can be found in the following paper:

Some perfect matchings and perfect half-integral matchings in NC.
Raghav Kulkarni, Meena Mahajan and Kasturi R. Varadarajan.
Chicago Journal of Theoretical Computer Science , Volume 2008 Article 4.


---

### Answer by username_5 on 2011-03-30. Score: 1

I'll take "greatly influenced" as a soft constraint rather than as a reduction. In that sense, MANY problems in computational geometry have running times that are bounded by some combinatorial structure underlying them. for example, the complexity of computing an arrangement of shapes is directly linked to the intrinsic complexity of such arrangements.

Another, topical example of this is that various problems in point pattern matching have running times that boil down to estimating quantities like the number of repeated distances in a point set, and so on.


---

### Answer by username_6 on 2011-03-30. Score: 1

Not sure if this is what you were looking for but phase transitions of NP-Complete problems rely heavily on probabilistic arguments, which are just another form of counting.

[LLL](http://www.google.com/url?sa=t&source=web&cd=4&ved=0CDEQFjAD&url=http%3A%2F%2Fwww.farcaster.com%2Fpapers%2Fcrypto-sumcc%2Fsumcc.ps&rct=j&q=subset%20sum%20crypto%20lattice%20reduction&ei=N5uTTdvUMM-3tgf6_tBm&usg=AFQjCNFcHqW4nF8N0T2dRYacBrTsWRGJuQ&cad=rja) has been used to solve some 'low-density' Subset Sum problems, the success of which relies on high probability short lattice vectors existing that meet the criteria of being a Subset Sum solution. [Survey Propagation](http://arxiv.org/PS_cache/cs/pdf/0212/0212002v4.pdf) relies on the structure of solution space (and the number of solutions as it fixes variables) to find solutions near the critical threshold.

[Borgs, Chayes and Pittel](http://research.microsoft.com/en-us/um/people/jchayes/Papers/partitionSTOC.pdf) have pretty much completely characterized the phase transition of the (Uniform) Random Number Partition Problem and thus have characterized how many solutions one can expect for a given (random) instance of the Number Partition Problem.


---

