Some problems on which we cannot even get in the zone

 Rough on Ruff source

Lindy Ruff was recently named coach of the Dallas Stars in the National Hockey League. He was the coach of the Buffalo Sabres against the Stars 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 complexity-relevant problems that are so rough 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 Rigas 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 ${G}$, consider adjacency matrices ${A}$ of ${G}$ with arbitrary real weights on the edges. Define ${\vartheta(G)}$ to be the minimum over ${A}$ of the maximum eigenvalue of ${I - A}$ (for equivalent forms see this). Also let ${\alpha(G)}$ be the largest size of an independent set in ${G}$ and ${\theta(G)}$ the minimum number of cliques needed to cover the nodes of ${G}$, which is the same as the chromatic number of the complement of ${G}$. Lovász showed:

Theorem 1 For all ${n}$-vertex graphs ${G}$,

1. ${\alpha(G) \leq \vartheta(G) \leq \theta(G)}$, and

2. ${\vartheta(G)}$ is computable to ${m}$-place precision by semidefinite programming in ${\mathsf{poly}(n,m)}$ time.

Thus two classic ${\mathsf{NP}}$-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 ${G_1 \boxtimes G_2}$ to have an edge between ${(u_1,u_2)}$ and ${(v_1,v_2)}$ if and only if they are distinct and for ${i=1,2}$, either ${u_i = v_i}$ or ${(u_i,v_i)}$ is an edge in ${G_i}$. Note that

$\displaystyle \alpha(G_1 \boxtimes G_2) \geq \alpha(G_1)\alpha(G_2),$

so that the sequence ${\alpha(G^{\boxtimes k})}$ stays above ${\alpha(G)^k}$.

For an important example of inequality, consider the pentagon ${C_5}$. It has independence number 2, but its strong-square has 5 independent nodes: ${(u,u)}$ and four pairs involving one neighbor and one non-neighbor of ${u}$, ordered so that the first elements are distinct. 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 ${\sqrt{5}}$ if we send them in pairs using the independent nodes of ${C_5^{\boxtimes 2}}$. Taking this idea further prompted Shannon’s definition:

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

From the notation, “\Theta” for Shannon and “\vartheta” for ${\vartheta(G)}$, clearly Lovász felt he had defined a variant of the Shannon capacity. It is a well-behaved variant, since he also proved:

Theorem 3

1. ${\vartheta(G \boxtimes H) = \vartheta(G)\vartheta(H)}$, and hence

2. ${\alpha(G) \leq \Theta(G) \leq \vartheta(G)}$;

3. ${\vartheta(C_5) = \sqrt{5}}$, so ${\Theta(C_5) = \sqrt{5}}$.

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 ${\Theta(C_7)}$. 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 ${\Theta(G) \geq r}$, given a graph ${G}$ and a rational number ${r}$, decidable? Is it ${\mathsf{NP}}$-hard?

You would think that a simple coding concept, after provoking such a creative burst as the Lovász ${\vartheta(G)}$ 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 ${u}$ of the form

$\displaystyle u_n = a_1 u_{n-1} + a_2 u_{n-2} + \cdots a_d u_{n-d},$

where the coefficients and the initial conditions ${u_1 = b_1}$, …, ${u_d = b_d}$ are all rational. The question is simply, does there exist ${n}$ such that ${u_n = 0}$? 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 ${Z_u}$ of ${n}$ such that ${u_n = 0}$, including:

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

Indeed, if we do not insist that periodic sets ${a + m\mathbb{N}}$ have ${a < m}$, 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 ${u}$ computes numbers ${a_1,\dots,a_r}$ and ${m_1,\dots,m_r}$ such that for some finite set ${F}$,

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

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

1. Whether ${Z_u}$ is infinite.

2. Whether ${Z_u}$ is co-finite.

3. Whether ${Z_u \neq \mathbb{N}}$.

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

Given ${u}$, is ${Z_u \neq \emptyset}$?

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

This equivalent form of the problem makes it seem even more innocent: given a ${d \times d}$ integer matrix, does it have a power whose ${1,d}$ entry is zero? However, many generalizations where we ask about products taken from a finite set of matrices, even just a set of seven ${3 \times 3}$ 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 ${\mathbb{Z}}$ and solvability over ${\mathbb{Q}}$. 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 ${\mathbb{Z}}$ as opposed to ${\mathbb{N}}$ or ${\mathbb{N^+}}$, but it is not hard to see that those cases are inter-reducible. As for ${\mathbb{Q}}$—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 ${p(x_1,\dots,x_n) = 0}$ with ${p}$ a polynomial of total degree ${d}$, introduce a new variable ${z}$ and create

$\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}).$

We can use the same ${z}$ for each ${x_i}$ 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 ${\mathbb{Z}}$ with ${z \neq 0}$ if and only if the original has a solution over ${\mathbb{Q}}$. Completing the reduction without the ${z \neq 0}$ exception involves going through the non-negative cases, as here and above in Wikipedia’s article.

Sounds like an equivalence, right? Well I might confess to the trap of thinking so, as I was unaware of the difference between the problems for a long time—though I mainly cared that these and all related solvability problems are ${\mathsf{NP}}$-hard. And it follows immediately that if the problem is decidable over ${\mathbb{Z}}$ then it is over ${\mathbb{Q}}$. This was certainly Hilbert’s expectation: the words in German do not 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”?

[fixed z=0 issue; fixed inequality and statement about the k-fold strong power of G; computing Lovász vartheta uses SDP not LP.]

1. July 11, 2013 1:21 am

Actually German soll ranges between English shall and should, and perhaps this weakens Hilbert’s exhortation to have the tone, “The objective is to give a procedure that can decide whether…”

• July 11, 2013 10:28 am

One can hardly avoid thinking of Dedekind’s “Was sind und was sollen die Zahlen?”, combining as it does the descriptive and normative aspects of number theory.

2. July 11, 2013 3:25 am

$\boxtimes = \text{Hard}~\times ?$

July 11, 2013 6:36 am

$\boxtimes$ = Strong Product.

• July 11, 2013 7:21 am
July 11, 2013 7:25 am

The obvious reduction of the Q-polynomials to Z-polynominals has a slight gap: What if p’ has a solution with z=0? Concrete example take p = x^2+1, then p’ = x^2+z^2 which has the solution (0,0), but p does not.

• July 11, 2013 9:19 am

Oh, good point, thanks. I was hoping to avoid giving kludgey details about Q^+ and N^+. I’ve patched this with a reference to the Wikipedia article.

5. July 11, 2013 8:04 am

The “zone” in statistics is the probability model or the reference class of distributions. Make the right choice and everything goes swimmingly, but until then we are just treading water. (Sorry about mixing sports metaphors — think swimsuit issue if that helps.)

Viewed from the Peircean press box, that is just the problem of abduction in scientific inference all over again. Certainly our bidden and unbidden samples of prior data inform the choice of reference class, but that initial hypothesis tends to go beyond the data, being greatly under-determined by the given.

6. July 11, 2013 10:03 am

I do know that the correlation between replacing coaches and CEOs, and an improvement in performance is zero. Some people claim to perceive a difference but that is either the human habit of seeing patterns in randomness or regression to the mean. There is some correlation in changing film studio execs but this is because of the time it takes to produce a film. When a new CEO takes over, 100% of the films that start coming out were projects started by his predecessor.

July 11, 2013 4:07 pm

I look forward to your discussion of the decidability of the Shannon capacity vis-a-vis Brendan Shanahan’s capacity for making good decisions .

We could take a lesson from the Ryan Miller / Milan Lucic encounter: attacking a hard problem with weak tools can give you a headache.

• July 11, 2013 7:21 pm

LOL—in fantasy football that capacity was already taken up by coach Mike Shanahan, trying to figure his use of running backs. Yeah, Miller and teammates still have to learn the lesson about “sticks and stones…” in the NHL.

8. July 11, 2013 8:40 pm

Here’s a bit from my old dissertation proposal that used to be titled “Puck, the Ref”, roughly in commemoration of some fracas on the ice at the time.

July 12, 2013 5:06 am

Few things:

1) If the independence number of a graph on $n$-vertices is known (and may be we have a proof of the maximum independent set), what is the independence number of its strong product with itself? This is not known to be NP-complete/NP-hard

2) Wouldn’t it be reasonable to thing if the independence number of a class of graph on $n$-vertices is NP-complete, then determining its Shannon capacity is atleast NP-hard?

In a way Lovasz started a revolution in graph theory. Embedding graphs in Hilbert spaces and deriving properties of their combinatorics. Reminds of Descartes’ approach to geometry.

July 12, 2013 5:07 am

In point 2) thing = think.

10. July 17, 2013 4:47 pm

There has been a renewed interest in Lovász theta and Shannon capacity among quantum computing people. For example, see [http://arxiv.org/abs/quant-ph/0608016], [http://arxiv.org/abs/1002.2514], [http://arxiv.org/abs/1009.1195], [http://arxiv.org/abs/1212.1724]. The idea is that you can define various graph-theoretic quantities in terms of games with a prover and non-interacting verifiers. Then you can get “quantum” analogues of such quantities by allowing the provers to share entanglement and use quantum strategies. This has resulted in a whole range of new quantities and inequalities between them. In most cases it is not known whether these inequalities are tight or not. Decidability or hardness of these new quantities is also often not known.

July 18, 2013 5:09 am

@Maris Ozols: Isn’t the situation like Riemann Hypothesis. “Hey guys, you know what. We cannot solve the original RH. So lets redefine the problem for number fields, automorphic forms etc etc and get our pay checks and tenure. You know we are from MIT, Stanford, Berkeley, GaTech, UChicago and big glass boxes. Let the other poor souls praise us.” Other than Lovasz, no one really has contributed to the problem.

11. August 10, 2013 10:18 am

Interesting – thanks! A typo: the inequality $\alpha(G_1 \boxtimes G_2) \geq \alpha(G_1)\alpha(G_2)$ is the wrong way round.

• August 10, 2013 10:59 am

Sorry to be finding fault again, but this comment of Tobias Fritz casts doubt on the claim that the sequence $\alpha(G^{\boxtimes k})^{1/k}$ is always nondecreasing. Taking $G = C_5$ and $k = 2, 3$ seems to show that this can’t be the case.

• August 10, 2013 11:14 am

Thanks! The latter statement I picked up from a reference to how the sup in the definition of Shannon capacity becomes a limit, I guess too glibly.

12. August 13, 2013 10:36 pm

$\theta(G)$ isn’t really computable by the usual linear programming (unless $G$ is very special), one needs to do linear programming over the cone of positive semidefinite matrices, a.k.a. semidefinite programming.

• August 13, 2013 10:51 pm

You are right—thanks for “backchecking” :-).

13. March 7, 2016 9:38 pm

With the linear recurrences problem, I recall a paper by Blondel Tsitkilis that had an interesting computational model involving linear transformations which they showed had undecidable properties. Wonder how it would relate to this problem.