Using lower bounds to prove non-structure theorems

Christos Papadimitriou is one of the most prolific researchers in all of theory. Who else has written as many important papers, written great textbooks, written fiction–a novel entitled fittingly Turing, written a comic book, and who gives such terrific talks? No one else. Christos also has the unique combination of being able to solve long standing open problems, and also create entire new fields and areas of theory. I am proud that my Papadimitriou number is one–I am not sure if he still remembers that we wrote a paper together, it was so long ago.

Today I would like to talk about a philosophical idea that Papadimitriou has raised over the years. I find his idea very intriguing, even if–as you know–I am not convinced of his basic premise. His idea is:

$\displaystyle \text{P} \neq \text{NP} \rightarrow \text{ certain non-structure theorems. }$

Thus, the fundamental idea is that if P is not equal to NP, then there cannot be “structural theorems” for many problems. This is an extremely interesting idea, which could have far-reaching consequences. Of course, I have to explain what a “non-structure theorem” is, but you probably have some idea from the name alone.

I know several stories about Christos–one concerns Gödel’s initial draft of the proof of his Incompleteness Theorem, but I rather give one today about his PhD advisor Ken Steiglitz, who is on the faculty at Princeton. Christos and Ken have worked together over the years, and somehow telling a story about Ken seems appropriate. Maybe it indirectly sheds light on Christos, maybe not.

In 1980 I had just joined the faculty at Princeton, and my first “task” was to try and recruit David Dobkin to come to Princeton. One night, during David’s job visit, David and Ken were discussing various topics at my house at the end of a party. At one point Ken started to talk about how much he loved professional wrestling–yes that’s right–professional, slam on the mat, wrestling. I did not know Ken well at that time, and I began to get nervous that David would think we were strange and would not come. Ken said he loved going to matches and was a real fan; he knew the names of the stars and many stats about wrestling, which made it clear he was not joking.

I finally jumped in and said, “but Ken, pro wrestling is fixed.” Without a moment’s hesitation Ken answered:

“That’s like saying Hamlet is fixed.”

I was speechless. David loved it and came to Princeton.

Halting Theorem Consequences

There is a simple analogy to Christos’ idea based on viewing Turing’s famous result that the Halting problem is undecidable as a “lower bound” result. The undecidability of the Halting problem implies that there can be no “structural theorem” that classifies all possible ways a machine can fail to halt. We can make a list of some ways that programs loop forever, for example:

• Have a loop with no termination condition;
• Have a loop with a termination condition that can never be satisfied. For example, loop until ${x>2}$ is an even prime;
• Have a loop that keeps changing the stopping condition. This is like constantly raising the bar for someone to succeed, as long as the bar keeps going up they will never succeed.
• ${\dots}$

Yet, no matter how clever our list is, the list will always be partial. There will always be programs that escape the list, yet do not halt. For those who are interested in this phenomena it is related to the notions of creative and productive sets in recursion theory. For those who are not interested, it still is related.

John McCarthy’s ${91}$ function is a cool example of how hard proving halting can be for even simple programs. The McCarthy function is recursive:

$\displaystyle M(n) = \begin{cases} n-10, \quad \text{if } n > 100 \\ M(M(n+11)), \quad \text{if } n \le 100. \end{cases}$

If you have not seen this function before, it is not obvious–I think–what the function does. The surprise is that the function always halts. Don Knuth has an even harder example of this type of function.

P Not Equal to NP Consequences

Papadimitriou’s insight is that just as there can be no structure theorems for halting, provided we assume P is not NP, there can be no structural theorems for a huge collection of problems. Roughly, any problem that is NP-complete will not have a theorem that gives a “good” characterization of the NP-complete property.

${\bullet}$ Consider the simple question of what is the characterization of graphs that are two colorable? This is easy: a graph is two-colorable if the vertices can be divided into two sets ${A}$ and ${B}$ so that all edges have one vertex in ${A}$ and one in ${B}$. Further, this division can be found fast by a simple greedy algorithm.

There can be no similar theorem for three colorable graphs since any reasonable characterization would lead to a proof that P=NP. It would be really great if there was some similar greedy algorithm for finding the coloring of a three colorable graph, but this is impossible unless P=NP.

${\bullet}$ Suppose that we consider another famous problem of finding a Hamiltoian Cycle (HC) in a graph. It is well known that this problem is NP-complete. Thus, Christos’ point is that graph theorists are unlikely to be able to find a condition ${C}$ so that (i) a graph ${G}$ has a HC if and only if ${C(G)}$ is true; (ii) the property ${C(G)}$ is checkable in polynomial time.

For example, there is the theorem due to John Bondy and Václav Chvátal: A graph is Hamiltonian if and only if its closure is Hamiltonian. Note, the closure of a graph is a new graph with the same vertices, but an edge is added between non-adjacent vertices ${x}$ and ${y}$ provided

$\displaystyle \text{deg}(x) + \text{deg}(y) \ge n$

where ${n}$ is the number of vertices. Since complete graphs are Hamiltonian, all graphs whose closure is complete are Hamiltonian. Of course, this does not come close to a structure theorem for HC, since sparse graphs can have a HC.

What Are Structure Theorems?

I do not have a clean definition of what Christos means by a structure theorem. Instead of a formal definition, I will give two examples. One of the issues that we might wish to study is: what is a structure theorem?

${\bullet}$ The Fundamental Theorem of Arithmetic can be viewed as a structure theorem. In 1975 Vaughan Pratt used this theorem, and Fermat’s little theorem, to show that ${\mathsf{PRIMES}}$ is in NP ${\cap}$ co-NP. These are now called “Pratt Certificates.” We know today much more, but at the time it was important to show that primality testing was not too hard.

${\bullet}$ Hall’s Theorem on matching is another example of a structure theorem. This famous theorem of Philip Hall shows that matchings have “structure.” We can use this to show that proving that a bipartite graph does not have a perfect matching is easy. One need only guess a set of vertices ${S}$ that have at most ${|S|-1}$ neighbors. This shows that ${\mathsf{PERFECT}}$ is in NP ${\cap}$ co-NP. Again we know more today, but the point is, as with primality, that Hall’s theorem precludes a hardness result.

RCT

I really like the general idea of Christos, but I suggest that we generalize it as follows: Show that a complexity lower bound has consequences outside of complexity theory. The lower bound can be proved or conjectured. Thus, the example on three colorable graphs, shows that assuming P ${\neq}$ NP, then there can be no structural theorem. Earlier I have written about related ideas based on factoring. For example, if factoring is hard, then certain identities for the ${\Gamma(z)}$ function cannot exist.

I tried to think of a good name for this type of result, and I suggest Reverse Complexity Theory. I hope this captures the idea that we are using complexity theorems to prove theorems in another area. Hence, the term “reverse.” If anyone has a better name please let me know. We could call it the Papadimitriou Principle, but ${\mathsf{PP}}$ was already taken as a complexity class.

The reason for studying RCT is two-fold. First, it would be great to get results outside of complexity theory that are based on complexity theory. A measure of the worth of a mathematical theory is often the ability of the theory to solve problems that come from another area. We expect a lower bound to imply another lower bound; however, we are surprised when a lower bound implies some result from a completely different part of theory or mathematics.

Second, the study of RCT could lead to a contradiction. It would be great if we could show that some unproved lower bound implies a contradiction in another area. This would be a terrific way to show that the lower bound is incorrect. The question of how fast can we compute factorials has exactly this goal in mind.

An Example

I think that RCT is a very interesting direction. We should try to see what structural theorems are missing under P ${\neq}$ NP and other related complexity assumptions. Here is one example, which I shall try to outline here. It is based on joint work with Nikhil Devanur and Nisheeth Vishnoi:

${\bullet }$ Show that, assuming the polynomial time hierarchy does not collapse, that Hilbert’s ${17^{th}}$ has lower bounds on the complexity of the rational functions used.

I need to explain what Hilbert’s ${17^{th}}$ problem is and why it is related to polynomial hierarchy. David Hilbert asked the following simple question: when can a polynomial,

$\displaystyle f(x) \ge 0$

for all ${x=(x_{1},\dots,x_{n})}$ real numbers? One obvious way is if ${f(x)}$ is equal to the sum of squares of polynomials. Thus, ${2x^{2} -2xy +y^{2}}$ is always non-negative, since it is equal to ${x^{2} + (x-y)^{2}}$. Hilbert realized that in general such a simple decomposition may not be possible. However, he conjectured that ${f(x)}$ is always non-negative if and only if it can be written as the sum of squares of rational functions.

This was proved, in 1927, by Emil Artin via the theory of real-closed fields, without any explicit bounds; later in 1967 Albrecht Pfister proved that any non-negative polynomial ${f(x)}$ over the reals can be written as the sum of squares of at most ${2^{n}}$ rational functions.

Since then there has been quite a bit of work on making these proofs more constructive. The main focus has been on two things: the number of rational functions required and the form of the rational functions. The best known lower bound–I believe–is that ${n+2}$ rational functions are required in some cases. Without regard to the number of rational functions, one can control the form of the rational functions. For example, it is possible to have the same denominator for all the rational functions and have their numerators all be powers of linear functions.

An obvious complexity question that one can ask is: what is the sum of the arithmetic complexities of the rational functions? I do not know of any non-trivial bounds here. What we proved in is that based on the assumption that the polynomial time hierarchy is strict, either there must be many rational functions, or that their straight-line complexity is high. This seems like a nice example of a RCT result.

Open Problems

The obvious open problems are to try and prove more RCT type theorems. Here is a short list of some possible reverse complexity theorems that we might be able to prove:

${\bullet }$ Show that assuming graph isomorphism is hard, that the famous graph reconstruction conjecture is false.

${\bullet }$ Show that assuming NP ${\neq}$ co-NP, that new lower bounds hold on Ramsey numbers.

${\bullet }$ Show that assuming that low degree polynomials modulo $6$ cannot compute majority, that certain group theory results are true.

I have more details to share in the future on the last two ideas; I realize they may be cryptic, but I will have to explain them another time.

$\displaystyle \S$

P.S. Am off to STOC and will be on Twitter from there $\dots$

May 30, 2009 9:54 am

This impossibility of structure theorems has been recurring theme in recursion theory, and in fact it motivated a lot of work in the 50’s. For example, Markov’s work on the undecidability of the homeomorphism problem for 4-manifolds. The philosophical meaning of the result is that 4-manifolds cannot be classified.

May 30, 2009 11:17 am

Yes. Similar results are of course known for infinite groups etc

May 30, 2009 10:26 am

May 30, 2009 11:16 am

Its rjlipton also can click on site I believe to join

3. May 30, 2009 3:38 pm

Just a note: Michael Freedman has proven that, assuming P^{#P} != NP, an interesting theorem A in knot theory holds (with no obvious connection to computation). According to Freedman, Theorem A seems impossible to prove without assuming the separation.

May 30, 2009 3:43 pm

Wow. That is cool. Will have to try and figure out the paper. Thanks for the pointer.

4. May 30, 2009 5:31 pm

I would be overjoyed to see some RCT consequences “on the ground”, and not just for large cardinals and other Ramsey-theoretic objects. My favourite result showing surprising and “human-scale” differences as a consequence of different axioms is the chromatic number of the plane, where in ZF+AC 4 colours are enough, but in ZF+LM+DC at least 5 are needed.

May 30, 2009 10:50 pm

great post as usual. i really enjoyed Ken Steiglitz’s story. it is probably the best of all the stories i have read in your blog.

6. May 31, 2009 4:00 am

RCT seems like a very interesting idea. Although I didn’t become interested in complexity until recently, it’s always seemed a little lopsided to me that complexity results borrow from so many other fields while giving less in return. For example, work by Cohn and Umans (and some other people I’m forgetting) shows that a conjecture about the existence of groups with a certain property implies an O(n^2) algorithm for matrix multiplication, but what would be very interesting is if there was some implication in the other direction.

7. June 1, 2009 1:29 pm

I like to add something about the importance of an extra condition/property C of finding a Hamiltoian Cycle (HC) in a graph. The following Hamiltonian Cycle (HC) problem is a well-known conjecture:

Barnette’s Conjecture (1969): Every graph that is 3-connected, 3-regular, bipartite and planar has a Hamiltonian cycle.

In a recent paper I have proposed an algorithmic proof for this conjecture by introducing an extra condition/property C. The condition is that, the graph satisfying properties of the conjecture has a specific Hamiltonian cycle which has a single “chamber”, where chamber is a collection of cycles those deletion results a Hamiltonian cycle. In this way original problem is reduced to find specific Hamiltonian path by the deletion (the door-edges) in the chamber cycle.