{\huge Rough Problems}

Some problems on which we cannot even get in the zone

\vspace{.5in}

Lindy Ruff was recently named coach of the Dallas Stars in the National Hockey League. He was the coach of the Buffalo Sabres in the 1999 Stanley Cup Finals, which ended with the infamous ``No Goal'' overtime game. That series and controversy made Dallas the most hated team in the Buffalo area for a long time, even more than the Boston Bruins. Ruff's 16 years coaching one team were far and away the longest active tenure in the NHL, until he was fired this past February. He also played 10 seasons for the Sabres in 1979--89 as a scrappy defenseman, living up to his name by averaging one penalty per game.

Today Dick and I want to talk about some problems so rough that we don't even know whether they are decidable.

At a public rally in Buffalo the day after the 1999 loss, John Rigas, then the Sabres owner and CEO of Adelphia Communications, referenced Winston Churchill in proclaiming that he would give Ruff ``the tools to finish the job.'' Alas he shortly took both his company and his team into bankruptcy, before his conviction for fraud in 2004. The team came close to reaching the Finals again in 2006 and 2007, but several times has been unable to keep star players who could have furnished ``the tools.'' In my opinion, until last year, Ruff always got more wins out of his players than views of their individual talents in fantasy-hockey projections led me to expect. But that can only go so far.

As complexity theorists we like to think about whether we can make heuristic algorithms for problems exact and efficient, and whether we can make exact algorithms better, using combinatorial tools at our disposal. How much resources of various types---time, space, randomness, guesses---does this require? These are the main issues that we like to think about. But there are some problems on which we are completely lost, where we seem to have a full roster of tools but they've been ineffective. Let's look at a few of them.

The Coach is Tough

Our first problem served as the motivational ``coach'' for the discovery of a remarkable polynomial-time computable invariant of graphs by László Lovász in 1979. Given a simple undirected graph $latex {G}&fg=000000$, consider adjacency matrices $latex {A}&fg=000000$ of $latex {G}&fg=000000$ with arbitrary real weights on the edges. Define $latex {\vartheta(G)}&fg=000000$ to be the minimum over $latex {A}&fg=000000$ of the maximum eigenvalue of $latex {I - A}&fg=000000$. Also let $latex {\alpha(G)}&fg=000000$ be the largest size of an independent set in $latex {G}&fg=000000$ and $latex {\theta(G)}&fg=000000$ the minimum number of cliques needed to cover the nodes of $latex {G}&fg=000000$, which is the same as the chromatic number of the complement of $latex {G}&fg=000000$. Lovász showed:

Theorem 1 For all $latex {n}&fg=000000$-vertex graphs $latex {G}&fg=000000$,
  1. $latex {\alpha(G) \leq \vartheta(G) \leq \theta(G)}&fg=000000$, and
  2. $latex {\vartheta(G)}&fg=000000$ is computable to $latex {m}&fg=000000$-place precision by linear programming in $latex {\mathsf{poly}(n,m)}&fg=000000$ time.

Thus two classic $latex {\mathsf{NP}}&fg=000000$-hard quantities are interpolated---and often well approximated---by a polynomial-time computable quantity. Lovász, however, was originally trying to compute a different quantity, which Claude Shannon had introduced in coding theory. Define the strong graph product $latex {G_1 \boxtimes G_2}&fg=000000$ to have an edge between $latex {(u_1,u_2)}&fg=000000$ and $latex {(v_1,v_2)}&fg=000000$ if and only if they are distinct and for $latex {i=1,2}&fg=000000$, either $latex {u_i = v_i}&fg=000000$ or $latex {(u_i,v_i)}&fg=000000$ is an edge in $latex {G_i}&fg=000000$. Note that

$latex \displaystyle \alpha(G_1 \boxtimes G_2) \leq \alpha(G_1)\alpha(G_2),&fg=000000$

so that the sequence $latex {\alpha(G^{\boxtimes k})^{1/k}}&fg=000000$ is nondecreasing. For an important example of inequality, consider the pentagon $latex {C_5}&fg=000000$. It has independence number 2, but its strong-square has 5 independent nodes: $latex {(u,u)}&fg=000000$ and the four pairs involving one neighbor and one non-neighbor of $latex {u}&fg=000000$. Let each node be an alphabet symbol and let each edge connect two symbols that a noisy channel might flip into each other. The noise bumps us down to a binary alphabet if we send just one symbol, but we get effective alphabet size $latex {\sqrt{5}}&fg=000000$ if we send them in pair using the independent nodes of $latex {C_5^{\boxtimes 2}}&fg=000000$. Taking this idea further prompted Shannon's definition:

Definition 2 The Shannon capacity is given by $latex {\Theta(G) = \lim_{k\rightarrow\infty}\alpha(G^{\boxtimes k})^{1/k}}&fg=000000$.

From the notation, ``Theta'' for Shannon and ``vartheta'' for $latex {\vartheta(G)}&fg=000000$, clearly Lovász felt he had defined a variant of the Shannon capacity. It is a well-behaved variant, sincet he also proved:

Theorem 3
  1. $latex {\vartheta(G \boxtimes H) = \vartheta(G)\vartheta(H)}&fg=000000$, and hence
  2. $latex {\alpha(G) \leq \Theta(G) \leq \vartheta(G)}&fg=000000$.
  3. $latex {\vartheta(C_5) = \sqrt{5}}&fg=000000$, so $latex {\Theta(C_5) = \sqrt{5}}&fg=000000$.

The last seemed to promise that ``vartheta'' would be a powerful tool for computing the Shannon capacity. However, no one during Lindy Ruff's entire NHL career has ever be able to compute $latex {\Theta(C_7)}&fg=000000$. Or even show that it is computable to any given precision---because independence numbers in strong products can ``jump up'' by magnitudes that are large and unpredictable. These facts and some limited positive results are in a paper by Noga Alon and Eyal Lubetzky, which leaves the following wide open:

Is the problem of whether $latex {\Theta(G) \geq r}&fg=000000$, given a graph $latex {G}&fg=000000$ and a rational number $latex {r}&fg=000000$, decidable? Is it $latex {\mathsf{NP}}&fg=000000$-hard?

You would think that a simple coding concept, after provoking such a creative burst as the Lovász $latex {\vartheta(G)}&fg=000000$ and being bodychecked by heavies in decades since, would at least be narrowed down better than this.

An Eighty-Year-Old Problem

Two other rough problems are ones we have mentioned before, but we say a little more about the first of them. The first specializes the Halting Problem to linear recurrences $latex {u}&fg=000000$ of the form

$latex \displaystyle u_n = a_1 u_{n-1} + a_2 u_{n-2} + \cdots a_d u_{n-d}&fg=000000$

where the coefficients and the initial conditions $latex {u_1 = b_1}&fg=000000$, \dots, $latex {u_d = b_d}&fg=000000$ are all rational. The question is simply, does there exist $latex {n}&fg=000000$ such that $latex {u_n = 0}&fg=000000$? This is named for Thoralf Skolem or Charles Pisot. We would like to think that finite linear recurrences are the nicest-behaved inductive quantities we can imagine, and we imagine that Skolem thought he could knock it off after he proved some strong facts about the set $latex {Z_u}&fg=000000$ of $latex {n}&fg=000000$ such that $latex {u_n = 0}&fg=000000$, including:

Theorem 4 $latex {Z_u}&fg=000000$ is always a union of finitely many periodic subsets of $latex {\mathbb{N}}&fg=000000$, give-or-take a finite set.

Indeed, if we do not insist that periodic sets $latex {a + m\mathbb{N}}&fg=000000$ have $latex {a < m}&fg=000000$, we have the following algorithmic result, whose proof is included in this survey by Vesa Halava, Tero Harju, Mika Hirvensalo, and Juhani Karhumäki:

Theorem 5 There is an algorithm that given $latex {u}&fg=000000$ computes numbers $latex {a_1,\dots,a_r}&fg=000000$ and $latex {m_1,\dots,m_r}&fg=000000$ such that for some finite set $latex {F}&fg=000000$,

$latex \displaystyle Z_u = F \cup (a_1 + m_1 \mathbb{N}) \cup \cdots \cup (a_r + m_r\mathbb{N}).&fg=000000$

Note that it is equivalent to compute a single value $latex {m}&fg=000000$ that is a multiple of each $latex {m_i}&fg=000000$ and a possibly-larger finite set of numbers $latex {b_j}&fg=000000$ such that $latex {b_j + m\mathbb{N}}&fg=000000$ covers all the periodic sets, which is the form actually given in the survey. The proofs also allow one to minimize $latex {r}&fg=000000$ in such a representation, importantly telling whether $latex {r = 0}&fg=000000$. Thus the following are all decidable:

  1. Whether $latex {Z_u}&fg=000000$ is infinite.
  2. Whether $latex {Z_u}&fg=000000$ is co-finite.
  3. Whether $latex {Z_u \neq \mathbb{N}}&fg=000000$.

OK the last is trivial, but it highlights the craziness of the following not being known to be decidable even when $latex {d = 6}&fg=000000$:

Given $latex {u}&fg=000000$, is $latex {Z_u \neq \emptyset}&fg=000000$?

At least we know that this is $latex {\mathsf{NP}}&fg=000000$-hard, unlike the case of Shannon capacity. The $latex {\mathsf{NP}}&fg=000000$-hardness was proved in 2002 by Vincent Blondel and Natacha Portier. Known upper bounds for this and relaterd problems even for $latex {d=5}&fg=000000$, however, take us into strange classes above $latex {\mathsf{NP}}&fg=000000$, as we covered last year.

This equivalent form of the problem makes it seem even more innocent: given a $latex {d \times d}&fg=000000$ integer matrix, does it have a power whose $latex {1,d}&fg=000000$ entry is zero? However, the generalization where we ask about products taken from a finite set of matrices, even just a set of seven $latex {3 \times 3}&fg=000000$ integer matrices, are undecidable. That hints why this 80-year-old problem is rough.

Older Than the Stanley Cup?

The Stanley Cup is over 20 years older than the National Hockey League itself. It was commissioned in 1892 and first awarded to the Montreal Hockey Club the next spring. We speculate that David Hilbert was already thinking of Diophantine equations when he published his 1892 paper, ``On the Irreducibility of Total Rational Functions With Integer Coefficients,'' eight years before including the famous tenth problem on his list in 1900.

We wonder whether he saw the extent of the difference between solvability over $latex {\mathbb{Z}}&fg=000000$ and solvability over $latex {\mathbb{Q}}&fg=000000$. Actually his very statement seems to exude confusion between them:

[...M]an soll ... entscheiden, ..., ob die Gleichung in ganzen rationalen Zahlen lösbar ist.

Literally this is asking, ``whether the equation is solvable in whole rational numbers.'' What Hilbert meant by the term was solvability over $latex {\mathbb{Z}}&fg=000000$ as opposed to $latex {\mathbb{N}}&fg=000000$ or $latex {\mathbb{N^+}}&fg=000000$, but it is not hard to see that those cases are inter-reducible. As for $latex {\mathbb{Q}}&fg=000000$---note we just blogged that this name wasn't even introduced until 1895---there's an obvious reduction but it only goes one way. Given a Diophantine equation in the form $latex {p(x_1,\dots,x_n) = 0}&fg=000000$ with $latex {p}&fg=000000$ a polynomial of total degree $latex {d}&fg=000000$, introduce a new variable $latex {z}&fg=000000$ and create

$latex \displaystyle p'(x_1,\dots,x_n,z) = 0 \qquad\text{where}\qquad p' = z^d p(\frac{x_1}{z},\dots,\frac{x_n}{z}).&fg=000000$

We can use the same $latex {z}&fg=000000$ for each $latex {x_i}&fg=000000$ with the intent that it becomes the least common denominator of all the rationals involved in any solution. Thus the new system has a solution over $latex {\mathbb{Z}}&fg=000000$ if and only if the original has a solution over $latex {\mathbb{Q}}&fg=000000$.

Sounds like an equivalence, right? Well I might confess to the trap of thinking so, as I was unaware of the difference for a long time---though I mainly cared that these and all related solvability problems are $latex {\mathsf{NP}}&fg=000000$-hard. And it follows immediately that if\/ the problem is decidable over $latex {\mathbb{Z}}&fg=000000$ then it is over $latex {\mathbb{Q}}&fg=000000$. This was certainly Hilbert's expectation: the words in German don't ask ``is it decidable?'' but rather command, ``One shall decide...''

We covered this problem in 2009, 2010, and 2011, but not last year. We don't have much new to say about it in English, but we note a new paper released last month by Kirsten Eisenträger and Alexandra Shlapentokh. But even they refer in their introduction to:

...Hilbert's Tenth Problem over the field of rational numbers which, at the moment, seems out of reach.

That's rough. Dick adds that it is a real gap in our knowledge that for these fundamental questions we do not know whether or not they are even decidable. Perhaps the right approach is to study special classes of graphs, or bound the size of the exponential equations, or in the last problem bound the number of variables and/or degree of the equation(s). Yet even these special cases look hard.

Open Problems

Will any of these problems be solved before Buffalo wins a Stanley Cup? Will incremental progress work, or do they need new tools? Are they really instances of the cliché phrase, ``as hard as ABC''?