<p>If I understand your question correctly, a canonical example would be deciding if a graph $G$ has an Eulerian circuit: equivalent to checking that <em>$G$ is connected and</em> every vertex has even degree.</p>

CC BY-SA 3.0
2014-02-13T18:36:29.687Z
2014-02-14T16:24:39.840Z
2014-02-14T16:24:39.840Z
Sasho Nikolov
<p>This afternoon I was reading <a href="http://rjlipton.wordpress.com/2011/01/12/stringology-the-real-string-theory/">Stringology -- the "Real" string theory</a>.</p>

<p><strong>Problem:</strong> If $x$ and $y$ are two strings over some alphabet when are there some positive integers $m, n$ such that $x^m = y^n$.</p>

<p><strong>Theorem:</strong> There are positive integers $m,n$ such that $x^m = y^n$ if and only if $xy = yx$.</p>

CC BY-SA 3.0
2014-02-13T03:38:10.193Z
2014-02-13T03:38:10.193Z
Pratik Deoghare
<p>Finding the number of (distinct) real roots of a real polynomial, either in all of ℝ or in a given interval. Sturm's theorem tells you that a sequence of polynomials that fulfils a small number of requirements can be used to count the number of real roots of a polynomial with real coefficients.</p>

<p>Then, all you have to do is construct such a sequence (which isn't very difficult, but requires some edge cases and handling of the case of non-separable polynomials), and Bob's your uncle.</p>

<p>Surprisingly, few people know about this result, despite it being quite old (1829). It is used in many Computer Algebra Systems, but all the mathematics professors at my university whom I asked either didn't know Sturm's Theorem at all or they only knew it by name and that it has something to do with roots of polynomials.</p>

<p>Most people are quite surprised when you tell them that something like <em>counting</em> real roots <em>exactly</em> is this easy and does not require any approximation, considering that <em>finding</em> roots is much more difficult. (Remember that for polynomials of degree ≥ 5, there does not even exist a “proper” formula for roots)</p>

CC BY-SA 3.0
2014-02-17T18:16:44.270Z
2014-02-17T18:16:44.270Z
Manuel Eberl
<blockquote>
  <p><strong>Theorem:</strong> Every planar graph has a vertex with degree at most 5.</p>
</blockquote>

<p><strong>Problem:</strong> Design an $O(n)$ representation of planar graphs where we can check if $(u, v)$ is an edge in $O(1)$ time. </p>

<p>We can remove the vertex with degree at most 5, and add it to a list as a key and its neighbors as values. The remaining graph is also planar and has a vertex with degree at most 5. So the space consumed is at most $5n$. We can check if $u$ is in the adjacency list of $v$; if not we can check if $v$ is in the adjacency list of $u$. This takes at most $10$ steps. </p>

CC BY-SA 3.0
2015-11-10T01:49:26.957Z
With a little more care you can reduce the size of the list stored at each vertex to 3 and the number of steps to check adjacency to 6. See: Planar orientations with low out-degree and compaction of adjacency matrices. M. Chrobak and D. Eppstein. Theor. Comp. Sci. 86 (2): 243–266, 1991. http://www.ics.uci.edu/~eppstein/pubs/ChrEpp-TCS-91.pdf
David Eppstein
CC BY-SA 3.0
2014-03-01T23:17:32.273Z
2015-11-12T09:20:34.300Z
2015-11-12T09:20:34.300Z
Pratik Deoghare
<p>I think the posterchild for this category, at least as far as difficulty assymetry is concerned, is the following problem:</p>

<p>Given a planar graph $G$, is $G$ 4-colourable?</p>

<p>The <a href="https://en.wikipedia.org/wiki/Four_color_theorem">Four colour theorem</a> simplifies the algorithm to <code>return true</code>.</p>

CC BY-SA 3.0
2015-11-10T01:44:26.430Z
2015-11-10T01:44:26.430Z
Jonas Kölker
<p>Whether a real (multivariate) polynomial $p$ can be expressed as a sum of squares of real polynomials can be solved by reduction to semi-definite programming. Need to know SDP and that SDP can be solved efficiently. </p>

CC BY-SA 3.0
2014-02-17T21:44:10.563Z
2014-02-17T21:44:10.563Z
Chandra Chekuri
<p>Another example: given an undirected graph, does it have a minimum cut in which all the edges are disjoint? If so, find one.</p>

<p>At first sight this might appear hard. It becomes easy, however, if you know the result that an undirected $n$-vertex graph can have at most $n(n-1)/2$ minimum cuts, and they can all be listed in polynomial time. </p>

<p>It can be extended to nearly-minimum cuts, which are larger than the minimum cut, but at most by a constant factor. Their number is still bounded by a polynomial. </p>

<p>(I did not search for a reference, my recollection is that these results are due to D. Karger.) </p>

CC BY-SA 3.0
2014-02-14T13:52:01.290Z
2014-02-14T13:52:01.290Z
Andras Farago
<p><strong>Decisional Diffie Hellman</strong></p>

<p>It states: given $(g, g^a, g^b, g^c)$ where $g$ is some generator of a cyclic group $\mathbb{G}$, verify if $g^c = g^{ab}$</p>

<p>Under the standard assumptions of hardness of discrete log problem, this problem may also seem hard.</p>

<p>However, with bilinear maps this problem is easy and can be verified as 
$$e(g,g^c) \stackrel{?}{=} e(g^a,g^b)$$</p>

<p>where $e: \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$</p>

<p>More about this can be read on <em>The decisional diffie-hellman problem</em>, Boneh'98 or a google lookup on Pairings</p>

CC BY-SA 3.0
2014-02-14T04:19:57.440Z
2014-02-14T04:19:57.440Z
Subhayan
<p>A slightly more complicated example: <a href="http://arxiv.org/pdf/1111.0952v1.pdf" rel="nofollow">nonnegative matrix factorization</a>, when the nonnegative rank is constant.</p>

<p>Say I give you a matrix $A \in M_{m \times n}$ along with the promise that there exist nonnegative $U \in M_{m \times k}$, $V \in M_{k \times n}$ such that $A = UV$. The problem is to find such a factorization for $A$.</p>

<p>With a few lines of elementary linear algebra you can reduce the problem to solving a system of polynomial inequalities in $O(r^2)$ variables, where $r$ is the nonnegative rank of the matrix you want to factor.</p>

<p>Using <a href="http://www.sciencedirect.com/science/article/pii/S0747717110800033" rel="nofollow">Renegar's algorithm</a> as a hammer, you can then solve this in time $(mn)^{O(r^2)}$ and hence recover $U$ and $V$. This is not far from optimality, since it's ETH-hard to solve NMF in time $(mn)^{o(r)}$.</p>

CC BY-SA 3.0
2014-02-14T03:37:50.667Z
2014-02-14T03:43:42.783Z
2014-02-14T03:43:42.783Z
zotachidil
<p><strong>Problem:</strong> Satifsiability of an MSO (monadic second-order logic) formula over finite words.</p>

<p><strong>Theorem:</strong> MSO is equivalent to finite automata over finite words.</p>

<p>The above can be lifted to infinite words, finite trees, infinite trees.</p>

CC BY-SA 3.0
2014-02-13T17:57:39.940Z
2014-02-13T17:57:39.940Z
Denis
<p>(Trivially) the existence of a Nash Equilibrium in a finite game, an even number of Hamiltonian Paths in a cubic graph, various types of fixed points, decently balanced comparisons in partial orders, and many other PPAD problems.</p>

CC BY-SA 3.0
2014-03-02T16:49:34.483Z
The existence of Nash Equilibrium - and many of the other proofs of existence that characterized PPAD - don't seem to make any of these problems any easier to solve algorithmically...
Joshua Grochow
CC BY-SA 3.0
2014-03-02T22:20:17.270Z
I was referring to the decision version of these problems.
Yonatan N
CC BY-SA 3.0
2014-02-14T02:40:41.430Z
2014-02-14T02:40:41.430Z
Yonatan N
<p>Here is another example: given an undirected simple graph, decide if it has two vertex-disjoint circuits. </p>

<p>One can naturally try to construct a recursive algorithm, by reducing the graph to a smaller one. This can be carried out easily, as long as the graph has a vertex with degree $\leq 2$. If, however, a graph is reached with minimum degree $\geq 3$, then it seems hard to find out how to continue, unless you know the following theorem (which originates in two papers, published independently by L. Lovasz and G. Dirac in 1965): </p>

<blockquote>
  <p><strong>Theorem.</strong> If a simple graph with minimum degree $\geq 3$  does not have two vertex-disjoint circuits, then the graph can only be one of the following three types: (1) $K_5$, (2) a wheel graph, (3) $K_{3,n-3}$, with possibly any edges added to the the 3-vertex class.</p>
</blockquote>

<p>Since it is easy to check whether a graph is one of the graphs allowed by the Theorem, this provides us with a polynomial-time algorithm for the decision problem. </p>

<p><em>Notes:</em> (1) The proof of the theorem is not at all easy. (2) Once we decided that two disjoint circuits exist, it  seems less clear how to solve the associated <em>search problem</em>, that  is, how to actually <em>find</em> such circuits. The theorem does not give direct advice to that.</p>

CC BY-SA 3.0
2014-02-17T18:59:25.060Z
2014-02-17T18:59:25.060Z
Andras Farago
<p>Finding min-cuts. Given a weighted graph and two vertices $((V, E), s, t)$, find $E' \subset E$ such that $s$ and $t$ are not connected in $(V, E')$, such that the total weight of $E'$ is maximised.</p>

<p>By the max-flow/min-cut theorem, this reduces to finding the maximum flow from $s$ to $t$ in $(V, E)$. This problem is not trivial, but a pretty simple idea works: if we can increase the flow along some $s$-$t$ path, do so. The tricky part is choosing which paths to augment in a way which finds the max-flow quickly.</p>

CC BY-SA 3.0
2014-02-17T21:41:01.193Z
One can say that flow is easy if you know that LP is easy. Thus two big theorems (LP in poly time and maxflow-mincut) allows us to compute min-cuts.
Chandra Chekuri
CC BY-SA 3.0
2014-02-18T11:13:25.707Z
@ChandraChekuri, my personal feeling is that that doesn't quite fit the question: the *theorem* that LP is solvable in polytime doesn't help us to actually constructed an algorithm for min-cuts. We need the actual LP algorithm.
Max
CC BY-SA 3.0
2014-02-20T15:31:03.720Z
Not really. If you can find the min-cut value in a given graph efficiently then you can use such an algorithm to find the actual cut itself.
Chandra Chekuri
CC BY-SA 3.0
2014-02-17T11:50:08.350Z
2014-02-17T11:50:08.350Z
Max
<p>less complex examples: there are some theorem-like properties that show that greedy algorithms for some problems are optimal. its not so obvious to the uninitiated a <a href="http://en.wikipedia.org/wiki/Minimum_spanning_tree" rel="nofollow">minimum spanning tree</a> can be found by a greedy algorithm. somewhat similar conceptually is <a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm" rel="nofollow">Dijkstra's algorithm</a> to find a shortest path in a graph. actually in both cases the associated "theorems" are nearly the same as the algorithms.</p>

CC BY-SA 3.0
2014-02-14T03:37:07.337Z
I think this will be a better answer if for example you include a statement of the cut property of MST and mention how it implies the correctness of a whole class of greedy MST algorithms.
Sasho Nikolov
CC BY-SA 3.0
2014-02-14T03:39:38.520Z
[MST cut property](http://en.wikipedia.org/wiki/Minimum_spanning_tree#Cut_property) listed on the wikipedia pg. maybe you can ref other generalizations not covered there. btw recall the questioner asked for examples serving _"those outside the theory field"_ (other nice examples given may be too advanced for outsiders)
vzn
CC BY-SA 3.0
2014-02-14T03:48:46.147Z
that cut property does not imply the correctness of the greedy algorithms as far as I can see. The property I mean is: a spanning tree $T$ is an MST if the following holds; for every edge $e$, $T - e$ has two connected components - let their vertices be $A$ an $B$; then $e$ is a minimum weight edge on the cut $E(A,B)$.
Sasho Nikolov
CC BY-SA 3.0
2014-02-14T02:49:09.543Z
2014-02-14T02:49:09.543Z
vzn
<p>Find the sequence of Fibonacci numbers that are the product of other Fibonacci numbers. For example, the Fibonacci number 8 is in the sequence because 8=2*2*2, and 2 is a Fibonacci number that is not equal to 8. The Fibonacci number 144 is in the sequence because 144=3*3*2*2*2*2, and both 2 and 3 are Fibonacci numbers that are not equal to 144.</p>

<p>Carmichael's theorem implies that 8 and 144 are the only terms of this sequence.</p>

CC BY-SA 3.0
2014-02-17T03:30:00.637Z
2014-02-17T03:30:00.637Z
Bob Lyons
<p>Deciding isomorphism of <em>simple</em> groups, given by their multiplication tables. The fact that this can be done in polynomial time follows directly from the fact that all finite simple groups can be generated by at most 2 elements, and currently the only known proof of that fact uses the Classification of Finite Simple Groups (perhaps the largest theorem - in terms of authors, papers, and pages - ever proven).</p>

CC BY-SA 3.0
2014-02-13T19:22:31.897Z
This is a great example! BTW the comments to this answer claim that in some sense this theorem is about as hard as the classification: http://mathoverflow.net/a/59216/35733
Sasho Nikolov
CC BY-SA 3.0
2014-02-13T18:59:47.570Z
2014-02-13T18:59:47.570Z
Joshua Grochow
<p>I am looking for nice examples, where the following phenomenon occurs: (1) An algorithmic problem looks hard, if you want to solve it working from the definitions and using standard results only.
(2) On the other hand,  it becomes easy, if you know some (not so standard) theorems. </p>

<p>The goal of this is to illustrate for students that learning more theorems can be  useful, even for those  who are outside of the theory field (such as software engineers, computer engineers etc). Here is an <b> example: </b></p>

<blockquote>
  <p><b> Question: </b> Given integers $n, k, l, d$, does there exist an $n$-vertex graph (and if so, find one), such that its vertex connectivity is $k$, its edge connectivity is $l$, and its minimum degree is $d$? </p>
</blockquote>

<p>Note that we require that the parameters are exactly equal to the given numbers, they are not just bounds. If you want to solve this from scratch, it might appear rather hard. On the other hand, if you are familiar with the following theorem (see <em> Extremal Graph Theory </em> by B. Bollobas), the situation becomes quite different.</p>

<blockquote>
  <p><b>Theorem: </b> Let $n, k, l, d$ be integers. There exists an $n$-vertex graph with vertex connectivity $k$, edge connectivity $l$, and minimum degree  $d$, if and only if one of the following conditions is satisfied: <UL>
  <LI>  $0\leq k\leq l \leq d &lt;\lfloor n/2 \rfloor$, 
  <LI> $1\leq 2d+2-n\leq k\leq l = d&lt; n-1$
  <LI> $k=l=d=n-1.$
  </UL></p>
</blockquote>

<p>These conditions are very easy to check, being simple  inequalities among the input parameters, so the existence question can be answered effortlessly. Furthermore, the proof of the theorem is constructive, resolving the construction issue, as well. On the other hand, this result does not appear standard enough, so that you can expect everybody to know about it.</p>

<p>Can you provide further examples in this spirit, where knowing a (not so standard) theorem greatly simplifies a task?</p>

CC BY-SA 3.0
2014-02-13T07:27:55.320Z
I am not sure I fully understand your questions. The example you give is a non-trivial problem for which Bollobas has given an algorithm (which implies a characterization). So my impression with your example is that any *non-trivial* algorithm will be an answer...
Bruno
CC BY-SA 3.0
2014-02-13T10:32:22.223Z
Primality and the AKS theorem.
Lamine
CC BY-SA 3.0
2014-02-13T13:48:57.440Z
@Bruno: What I mean is that the algorithmic task becomes much easier if you know a theorem, which is not well known, so one may have never heard of it. The presented example is not perfect in the sense that here the theorem does not just help, it actually solves the problem. What I am really looking for is when a theorem helps, provides some useful shortcut, but does not fully solve the problem in itself.
Andras Farago
CC BY-SA 3.0
2014-02-13T17:52:04.983Z
The other side is also extremely useful: when NOT to search for algorithms, based on theoretical considerations. The extreme case is undecidability (mortal matrix, wang tiles, halting), but also trying to approximate NP-complete problems is a nice outcome of the theory.
Denis
CC BY-SA 3.0
2014-02-13T22:53:37.213Z
Community wiki?
Joshua Grochow
CC BY-SA 3.0
2014-02-14T01:35:33.957Z
Note that, in the example you give, the theorem (an existence theorem) doesn't help with the question ("find one").
msh210
CC BY-SA 3.0
2014-02-14T02:52:28.650Z
on the other hand there are many hard algorithmic problems that are solved by complex theorems, but the resulting algorithms are complex... AKS primality testing, Shors algorithm, etc... not what you're looking for?
vzn
CC BY-SA 3.0
2014-02-14T22:35:54.943Z
Robertson–Seymour theorem, also conjectures that make deterministically finding primes easy.
Kaveh
CC BY-SA 3.0
2014-02-15T03:08:24.007Z
Just out of curiosity, in what page in the book can one find this theorem?
Obinna Okechukwu
<cc.complexity-theory><ds.algorithms><graph-algorithms>
Hard-looking algorithmic problems made easy by theorems
Andras Farago
# Hard-looking algorithmic problems made easy by theorems

(Asked by: username_0 on 2014-02-13)

I am looking for nice examples, where the following phenomenon occurs: (1) An algorithmic problem looks hard, if you want to solve it working from the definitions and using standard results only.
(2) On the other hand, it becomes easy, if you know some (not so standard) theorems.

The goal of this is to illustrate for students that learning more theorems can be useful, even for those who are outside of the theory field (such as software engineers, computer engineers etc). Here is an  **example:**

> **Question:**  Given integers $n, k, l, d$, does there exist an $n$-vertex graph (and if so, find one), such that its vertex connectivity is $k$, its edge connectivity is $l$, and its minimum degree is $d$?

Note that we require that the parameters are exactly equal to the given numbers, they are not just bounds. If you want to solve this from scratch, it might appear rather hard. On the other hand, if you are familiar with the following theorem (see  *Extremal Graph Theory*  by B. Bollobas), the situation becomes quite different.

> **Theorem:**  Let $n, k, l, d$ be integers. There exists an $n$-vertex graph with vertex connectivity $k$, edge connectivity $l$, and minimum degree $d$, if and only if one of the following conditions is satisfied:
>
> * $0\leq k\leq l \leq d <\lfloor n/2 \rfloor$,* $1\leq 2d+2-n\leq k\leq l = d< n-1$* $k=l=d=n-1.$

These conditions are very easy to check, being simple inequalities among the input parameters, so the existence question can be answered effortlessly. Furthermore, the proof of the theorem is constructive, resolving the construction issue, as well. On the other hand, this result does not appear standard enough, so that you can expect everybody to know about it.

Can you provide further examples in this spirit, where knowing a (not so standard) theorem greatly simplifies a task?

**Tags:** cc.complexity-theory, ds.algorithms, graph-algorithms

> **Comments:**
> **username_1**: I am not sure I fully understand your questions. The example you give is a non-trivial problem for which Bollobas has given an algorithm (which implies a characterization). So my impression with your example is that any *non-trivial* algorithm will be an answer...  
> **username_2**: Primality and the AKS theorem.  
> **username_0**: @username_1: What I mean is that the algorithmic task becomes much easier if you know a theorem, which is not well known, so one may have never heard of it. The presented example is not perfect in the sense that here the theorem does not just help, it actually solves the problem. What I am really looking for is when a theorem helps, provides some useful shortcut, but does not fully solve the problem in itself.  
> **username_3**: The other side is also extremely useful: when NOT to search for algorithms, based on theoretical considerations. The extreme case is undecidability (mortal matrix, wang tiles, halting), but also trying to approximate NP-complete problems is a nice outcome of the theory.  
> **username_4**: Community wiki?  
> **username_5**: Note that, in the example you give, the theorem (an existence theorem) doesn't help with the question ("find one").  
> **username_6**: on the other hand there are many hard algorithmic problems that are solved by complex theorems, but the resulting algorithms are complex... AKS primality testing, Shors algorithm, etc... not what you're looking for?  
> **username_7**: Robertson–Seymour theorem, also conjectures that make deterministically finding primes easy.  
> **username_8**: Just out of curiosity, in what page in the book can one find this theorem?  

---

## 16 answers

### Answer by username_4 on 2014-02-13. Score: 31 | Accepted answer

Deciding isomorphism of *simple* groups, given by their multiplication tables. The fact that this can be done in polynomial time follows directly from the fact that all finite simple groups can be generated by at most 2 elements, and currently the only known proof of that fact uses the Classification of Finite Simple Groups (perhaps the largest theorem - in terms of authors, papers, and pages - ever proven).

> **Comments:**
> **username_9**: This is a great example! BTW the comments to this answer claim that in some sense this theorem is about as hard as the classification: http://mathoverflow.net/a/59216/35733  

---

### Answer by username_9 on 2014-02-13. Score: 33

If I understand your question correctly, a canonical example would be deciding if a graph $G$ has an Eulerian circuit: equivalent to checking that *$G$ is connected and* every vertex has even degree.


---

### Answer by username_10 on 2014-02-13. Score: 20

This afternoon I was reading [Stringology -- the "Real" string theory](http://rjlipton.wordpress.com/2011/01/12/stringology-the-real-string-theory/).

**Problem:** If $x$ and $y$ are two strings over some alphabet when are there some positive integers $m, n$ such that $x^m = y^n$.

**Theorem:** There are positive integers $m,n$ such that $x^m = y^n$ if and only if $xy = yx$.


---

### Answer by username_11 on 2014-02-17. Score: 9

Finding the number of (distinct) real roots of a real polynomial, either in all of ℝ or in a given interval. Sturm's theorem tells you that a sequence of polynomials that fulfils a small number of requirements can be used to count the number of real roots of a polynomial with real coefficients.

Then, all you have to do is construct such a sequence (which isn't very difficult, but requires some edge cases and handling of the case of non-separable polynomials), and Bob's your uncle.

Surprisingly, few people know about this result, despite it being quite old (1829). It is used in many Computer Algebra Systems, but all the mathematics professors at my university whom I asked either didn't know Sturm's Theorem at all or they only knew it by name and that it has something to do with roots of polynomials.

Most people are quite surprised when you tell them that something like *counting* real roots *exactly* is this easy and does not require any approximation, considering that *finding* roots is much more difficult. (Remember that for polynomials of degree ≥ 5, there does not even exist a “proper” formula for roots)


---

### Answer by username_10 on 2014-03-01. Score: 9

> **Theorem:** Every planar graph has a vertex with degree at most 5.

**Problem:** Design an $O(n)$ representation of planar graphs where we can check if $(u, v)$ is an edge in $O(1)$ time.

We can remove the vertex with degree at most 5, and add it to a list as a key and its neighbors as values. The remaining graph is also planar and has a vertex with degree at most 5. So the space consumed is at most $5n$. We can check if $u$ is in the adjacency list of $v$; if not we can check if $v$ is in the adjacency list of $u$. This takes at most $10$ steps.

> **Comments:**
> **username_12**: With a little more care you can reduce the size of the list stored at each vertex to 3 and the number of steps to check adjacency to 6. See: Planar orientations with low out-degree and compaction of adjacency matrices. M. Chrobak and D. Eppstein. Theor. Comp. Sci. 86 (2): 243–266, 1991. http://www.ics.uci.edu/~eppstein/pubs/ChrEpp-TCS-91.pdf  

---

### Answer by username_13 on 2015-11-10. Score: 7

I think the posterchild for this category, at least as far as difficulty assymetry is concerned, is the following problem:

Given a planar graph $G$, is $G$ 4-colourable?

The [Four colour theorem](https://en.wikipedia.org/wiki/Four_color_theorem) simplifies the algorithm to `return true`.


---

### Answer by username_14 on 2014-02-17. Score: 6

Whether a real (multivariate) polynomial $p$ can be expressed as a sum of squares of real polynomials can be solved by reduction to semi-definite programming. Need to know SDP and that SDP can be solved efficiently.


---

### Answer by username_0 on 2014-02-14. Score: 5

Another example: given an undirected graph, does it have a minimum cut in which all the edges are disjoint? If so, find one.

At first sight this might appear hard. It becomes easy, however, if you know the result that an undirected $n$-vertex graph can have at most $n(n-1)/2$ minimum cuts, and they can all be listed in polynomial time.

It can be extended to nearly-minimum cuts, which are larger than the minimum cut, but at most by a constant factor. Their number is still bounded by a polynomial.

(I did not search for a reference, my recollection is that these results are due to D. Karger.)


---

### Answer by username_15 on 2014-02-14. Score: 4

**Decisional Diffie Hellman**

It states: given $(g, g^a, g^b, g^c)$ where $g$ is some generator of a cyclic group $\mathbb{G}$, verify if $g^c = g^{ab}$

Under the standard assumptions of hardness of discrete log problem, this problem may also seem hard.

However, with bilinear maps this problem is easy and can be verified as
$$e(g,g^c) \stackrel{?}{=} e(g^a,g^b)$$

where $e: \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}\_T$

More about this can be read on *The decisional diffie-hellman problem*, Boneh'98 or a google lookup on Pairings


---

### Answer by username_16 on 2014-02-14. Score: 4

A slightly more complicated example: [nonnegative matrix factorization](http://arxiv.org/pdf/1111.0952v1.pdf), when the nonnegative rank is constant.

Say I give you a matrix $A \in M\_{m \times n}$ along with the promise that there exist nonnegative $U \in M\_{m \times k}$, $V \in M\_{k \times n}$ such that $A = UV$. The problem is to find such a factorization for $A$.

With a few lines of elementary linear algebra you can reduce the problem to solving a system of polynomial inequalities in $O(r^2)$ variables, where $r$ is the nonnegative rank of the matrix you want to factor.

Using [Renegar's algorithm](http://www.sciencedirect.com/science/article/pii/S0747717110800033) as a hammer, you can then solve this in time $(mn)^{O(r^2)}$ and hence recover $U$ and $V$. This is not far from optimality, since it's ETH-hard to solve NMF in time $(mn)^{o(r)}$.


---

### Answer by username_3 on 2014-02-13. Score: 4

**Problem:** Satifsiability of an MSO (monadic second-order logic) formula over finite words.

**Theorem:** MSO is equivalent to finite automata over finite words.

The above can be lifted to infinite words, finite trees, infinite trees.


---

### Answer by username_17 on 2014-02-14. Score: 3

(Trivially) the existence of a Nash Equilibrium in a finite game, an even number of Hamiltonian Paths in a cubic graph, various types of fixed points, decently balanced comparisons in partial orders, and many other PPAD problems.

> **Comments:**
> **username_4**: The existence of Nash Equilibrium - and many of the other proofs of existence that characterized PPAD - don't seem to make any of these problems any easier to solve algorithmically...  
> **username_17**: I was referring to the decision version of these problems.  

---

### Answer by username_0 on 2014-02-17. Score: 2

Here is another example: given an undirected simple graph, decide if it has two vertex-disjoint circuits.

One can naturally try to construct a recursive algorithm, by reducing the graph to a smaller one. This can be carried out easily, as long as the graph has a vertex with degree $\leq 2$. If, however, a graph is reached with minimum degree $\geq 3$, then it seems hard to find out how to continue, unless you know the following theorem (which originates in two papers, published independently by L. Lovasz and G. Dirac in 1965):

> **Theorem.** If a simple graph with minimum degree $\geq 3$ does not have two vertex-disjoint circuits, then the graph can only be one of the following three types: (1) $K\_5$, (2) a wheel graph, (3) $K\_{3,n-3}$, with possibly any edges added to the the 3-vertex class.

Since it is easy to check whether a graph is one of the graphs allowed by the Theorem, this provides us with a polynomial-time algorithm for the decision problem.

*Notes:* (1) The proof of the theorem is not at all easy. (2) Once we decided that two disjoint circuits exist, it seems less clear how to solve the associated *search problem*, that is, how to actually *find* such circuits. The theorem does not give direct advice to that.


---

### Answer by username_18 on 2014-02-17. Score: 2

Finding min-cuts. Given a weighted graph and two vertices $((V, E), s, t)$, find $E' \subset E$ such that $s$ and $t$ are not connected in $(V, E')$, such that the total weight of $E'$ is maximised.

By the max-flow/min-cut theorem, this reduces to finding the maximum flow from $s$ to $t$ in $(V, E)$. This problem is not trivial, but a pretty simple idea works: if we can increase the flow along some $s$-$t$ path, do so. The tricky part is choosing which paths to augment in a way which finds the max-flow quickly.

> **Comments:**
> **username_14**: One can say that flow is easy if you know that LP is easy. Thus two big theorems (LP in poly time and maxflow-mincut) allows us to compute min-cuts.  
> **username_18**: @ChandraChekuri, my personal feeling is that that doesn't quite fit the question: the *theorem* that LP is solvable in polytime doesn't help us to actually constructed an algorithm for min-cuts. We need the actual LP algorithm.  
> **username_14**: Not really. If you can find the min-cut value in a given graph efficiently then you can use such an algorithm to find the actual cut itself.  

---

### Answer by username_6 on 2014-02-14. Score: 1

less complex examples: there are some theorem-like properties that show that greedy algorithms for some problems are optimal. its not so obvious to the uninitiated a [minimum spanning tree](http://en.wikipedia.org/wiki/Minimum_spanning_tree) can be found by a greedy algorithm. somewhat similar conceptually is [Dijkstra's algorithm](http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) to find a shortest path in a graph. actually in both cases the associated "theorems" are nearly the same as the algorithms.

> **Comments:**
> **username_9**: I think this will be a better answer if for example you include a statement of the cut property of MST and mention how it implies the correctness of a whole class of greedy MST algorithms.  
> **username_6**: [MST cut property](http://en.wikipedia.org/wiki/Minimum_spanning_tree#Cut_property) listed on the wikipedia pg. maybe you can ref other generalizations not covered there. btw recall the questioner asked for examples serving _"those outside the theory field"_ (other nice examples given may be too advanced for outsiders)  
> **username_9**: that cut property does not imply the correctness of the greedy algorithms as far as I can see. The property I mean is: a spanning tree $T$ is an MST if the following holds; for every edge $e$, $T - e$ has two connected components - let their vertices be $A$ an $B$; then $e$ is a minimum weight edge on the cut $E(A,B)$.  

---

### Answer by username_19 on 2014-02-17. Score: 1

Find the sequence of Fibonacci numbers that are the product of other Fibonacci numbers. For example, the Fibonacci number 8 is in the sequence because 8=2\*2\*2, and 2 is a Fibonacci number that is not equal to 8. The Fibonacci number 144 is in the sequence because 144=3\*3\*2\*2\*2\*2, and both 2 and 3 are Fibonacci numbers that are not equal to 144.

Carmichael's theorem implies that 8 and 144 are the only terms of this sequence.


---

