Arithmetic Hierarchy and P=NP

May 27, 2009

The complexity of open problems via the arithmetic hierarchy

images

Stephen Kleene is a famous logician who got his PhD under Alonzo Church at Princeton University. Kleene has many important concepts named after him: the Kleene hierarchy, the Kleene star, Kleene’s recursion theorem and the Kleene fixed-point theorem. His 1952 book, Introduction to Meta-mathematics, is a classic; more on his book in a moment, which while a classic has an unusual feature.

Today, I want to talk about the Kleene Hierarchy, which is now usually called the Arithmetic Hierarchy (AH). We can use the AH to classify problems, in a sense, that I will shortly make precise. In this classification, the P=NP question comes out with high marks, which is both cool–we have a hard open problem–and is uncool, since we have a hard open problem.

I had the honor of meeting Kleene at his retirement conference, which was held in June 1978 in Madison, Wisconsin. That summer I was also privileged to sit in the office of Barkley Rosser, who was away on leave. Somehow I thought a lot about logic that summer.

Kleene had many terrific PhD students: two I know well are Robert Constable and Richard Vesley. Richard, who is a wonderful teacher, taught me first order logic and recursion theory, and helped me solve my first “open” problem. But, that is another story, for another day.

There is a barber shop story about Kleene, which I cannot validate with certainty; and there is a retirement story that I can validate–since I saw it first hand.

While working for Church, Stephen was trying to show that the lambda calculus could compute anything “computable”. Unfortunately, Church and Kleene could not see how to compute even the following function:

$\displaystyle x \rightarrow x+1.$

Yes, even the lowly successor function was not obviously computable in their calculus. The story goes that one day Stephen was getting his hair cut, when he realized how to encode the successor function into the lambda calculus. It is claimed, he jumped out of the barber chair, with half a haircut, and ran to tell Church. Not quite Archimedes running naked through the streets of Syracuse, shouting “Eureka,” but close. I think the story, true or not, says more about the nature of the lambda calculus as a basis of computing than anything else, but that is my take.

At Kleene’s retirement conference the final talk was given by the great man himself. After a long and well deserved introduction Kleene stepped up to the stage, and placed his first overhead slide onto the projector. Before he could say a word there was a roar of laughter throughout the packed auditorium. He ignored the laughter and proceeded with his talk. The reason for the laughter was that the slide looked like a page from his famous book. The slide looked like this:

$\displaystyle 1. \dots$

$\displaystyle \vdots$

$\displaystyle \quad 1.1 \dots$

$\displaystyle \vdots$

$\displaystyle \quad \quad 1.1.1 \dots$

$\displaystyle \quad \vdots$

$\displaystyle 2. \dots$

Meta-mathematics his book, is known for its detailed numbering scheme that only a logician could love. Phrases like “by ${2.4.1}$ we see that ${2.7.4}$ is true” abound. We all thought that Kleene was making fun of his own style, and would soon switch into story mode. The audience stopped laughing as soon as it dawned on everyone that this was no joke. Kleene was going to read and present a very detailed argument on something. Too bad. I was hoping to hear stories about his advisor, or his results, or his students–his life. But that was not to be: we were treated to an hour of a detailed talk on some exotic topic in logic.

Arithmetic Hierarchy

The AH classifies all formulas according to their quantifier complexity. Thus, a sentence is in $\Pi_{2}$ provided it is equivalent to,

$\displaystyle \forall x \exists y \psi(x,y)$

and ${\psi(x,y)}$ is quantifier free.

For example, Fermat’s Last Theorem (FLT) is in $\Pi_{1}$ . This follows since we can write it in the following way.

$\displaystyle \forall x,y,z,n>2 \quad (x^{n}+y^{n} = z^{n} \rightarrow xyz=0)$

In a reversal of history, if you know the polynomial hierarchy, then you know AH: just remove the restrictions on the quantifiers. There was a time when many great ideas of complexity theory could be found by taking a concept from the area of recursion theory and “just” making the concept feasible: diagonalization, complete sets, various notions of reducibility, oracles, and more. That was not always how they were actually discovered, but many of the key notions were first defined in recursion theory. There may be other concepts still lurking there ${\dots}$

Classification of Open Problems

We saw how we could write the FLT in AH. In a natural way we can classify any open problem of arithmetic by writing it as a formal statement in AH. Here are some other problems–some open and some known–with respect to their AH complexity. This idea of viewing a problem’s complexity via the AH is an old idea, but one that I find useful. I hope you will agree.

${\bullet}$ The Four Color Theorem is in $\Pi_{1}$ . This is easy to see, since it states that for every planar graph, there is a ${4}$ -coloring of the faces.

${\bullet}$ The Finite Simple Group Classification is in $\Pi_{1}$ . This is the famous “conjecture”, that is now a theorem, that all finite simple groups are either one of the ${26}$ so-called sporadic simple groups, or come from the known infinite families of finite simple groups.

These first two raise a annoying point. If a theorem is proved, then it can be written as anything. This is another way of saying that ${1=1}$ is equivalent to the Four Color Theorem. What I mean above is: what is the best that you can do without using the proof of the theorem. Textbook exercises have this problem all the time: “without using X prove Y.” I have the same problem here.

${\bullet}$ The Jacobian Conjecture is in $\Pi_{1}$ . This is, one of my favorite non-complexity conjectures. I will discuss it another time. The fact that it is of this form is not trivial, since it concerns the behavior of polynomials with complex coefficients. It requires a lemma to re-state it as a statement about integers.

${\bullet}$ The Riemann Hypothesis is in $\Pi_{1}$ . The fact that this is in $\Pi_{1}$ is plausible, since it states, of course, that all the non-trivial roots of the ${\zeta(\sigma+it)}$ function have ${\sigma=1/2}$ . However, the obvious way to encode this runs into many technical issues about the locations of the zeroes of the ${\zeta(\sigma+it)}$ function. However, Jeff Lagarias to the rescue. He has proved the following wonderful result: Let ${H_{n}}$ be equal to the ${n^{th}}$ harmonic number,

$\displaystyle H_n = \sum_{i=1}^{n} \frac{1}{i}.$

Consider, the statement (E), that for all ${n \ge 1}$ ,

$\displaystyle \sum_{d | n} d \le H_{n} + \exp(H_{n})\log(H_{n})$

with equality only for ${n = 1}$ . Lagarias’ result is that the statement E is equivalent to the Riemann Hypothesis. This will show that the Riemann Hypothesis is in $\Pi_{1}$ .

Even with Jeff’s result there is a small technical point. We must show that it is computable to test whether or not

$\displaystyle a \le \exp(b)\log(c)$

for rational numbers ${a,b,c}$ . By clearing the denominator of ${a}$ and using the elementary fact that ${ r \log(c) = \log(c^{r})}$ , we can show that we need only be able to test

$\displaystyle a \le \exp(b)\log(c)$

for natural numbers. This is easy: compute the right-hand side until the error is below ${1/3}$ . Then, since ${a}$ is a whole number, there can be no mistake.

${\bullet}$ The Twin Prime Conjecture is in $\Pi_{2}$ . This is the famous conjecture that there are an infinite number of primes $p$ so that $p+2$ is also prime. Such a prime is, of course, called a twin prime. The obvious way to say this is: for all $x$ , there is a twin prime $p$ that is greater than $x$

Where is P=NP in the AH?

The next question is where does P=NP lie with respect to AH? I do not know if either one of P=NP or P ${ {\neq} }$ NP are in $\Pi_{1}$ . I will explain the best that I know, and I hope that someone can improve these simple bounds–perhaps they have already? Of course, as I pointed out earlier, if the P=NP question is resolved, then better bounds must follow.

First, lets look at how to encode P ${ {\neq} }$ NP. We need the standard idea of adding a “clock” to a Turing machine. Let ${[x,y]}$ be a pairing function on the natural numbers: that is ${x,y \rightarrow [x,y]}$ is one-to-one and is easy to compute. Define,

$\displaystyle M_{[x,c]}$

as the deterministic Turing machine that operates as follows on an input ${y}$ . The machine treats ${x}$ as a deterministic program, and simulates ${x}$ on input ${y}$ . At the same time the machine runs a counter that stops its execution after ${|y|^{c}}$ steps. If the machine accepts before the counter stops, then it accepts; otherwise, it rejects.

Then,

Theorem: P ${ {\neq} }$ NP is a $\Pi_{2}$ sentence.

Proof: Define ${ {\psi(x,c,y)} }$ to denote that

$\displaystyle M_{[x,c]}(y) = z$

and either (i) ${y}$ is in ${{\mathsf{SAT}}}$ and ${z}$ is “reject”, or (ii) ${y}$ is not in ${{\mathsf{SAT}}}$ and ${z}$ is “accept.” I claim that P ${ {\neq} }$ NP is equivalent to

$\displaystyle \forall x,c \, \exists y \, \psi(x,c,y). \ \ \ \ \ (1)$

Suppose that P ${ {\neq} }$ NP is true. Then, I claim that (1) is true. Suppose that it is false, then it follows that there are ${x,c}$ so that ${ M_{[x,c]}}$ correctly computes ${{\mathsf{SAT}}}$ . This is a contradiction.

Next suppose that P=NP. Then, I claim that (1) is false. Let ${x}$ be the program that runs in polynomial time and computes ${{\mathsf{SAT}}}$ correctly. Then, this is again a contradiction. $\Box$

Second, now let us look at how to encode P=NP. It is easy to see that it is a ${ {\Sigma_{2}} }$ sentence, since it is the negation of the first sentence, P ${ {\neq} }$ NP. Thus, P=NP is:

$\displaystyle \exists x,c \, \forall y \, \neg\psi(x,c,y)$

A question that I wonder about is : can we do better? Can we encode, for example, P ${ {\neq} }$ NP, as a $\Pi_{1}$ sentence?

A Curious Property of ${\mathsf{SAT}}$

We have shown that P ${ {\neq} }$ NP is a $\Pi_{2}$ sentence. Every such sentence can be viewed as defining a Skolem function. Recall if

$\displaystyle \forall x \, \exists y \, A(x,y)$

is true, then there is a function $f$ , called the Skolem function, so that for all $x$ , $A(x,f(x))$ .

Let ${f(i,c)}$ be the smallest natural number ${y}$ so that ${M_{[i,c]}}$ makes a mistake on the input ${y}$ . Then, if P ${ {\neq} }$ NP is true, the function ${f(i,c)}$ is always defined.

The curious property of this function is this. If ${f(i,c)}$ grows “fast” for an infinite number of inputs, then while P ${ {\neq} }$ NP, my nightmare happens. In this case, there are an infinite number of ${n}$ so that ${{\mathsf{SAT}}}$ for inputs of length ${n}$ has circuit size ${n^{O(\log n)}}$ .

Theorem: Suppose that there are infinite number of $i$ for which there exists a $c$ so that
$\displaystyle f(i,c) > 2^{2^{|i|+c}}.$
Then, for infinitely many ${n}$ , ${\mathsf{SAT}}$ has circuit size ${n^{O(\log n)}}$ .

Proof: Let ${i>1}$ and ${c}$ be so that

$\displaystyle f(i,c) > 2^{2^{|i|+c}}.$

Define ${n = 2^{|i|+c-1}}$ . Note, that ${c}$ is at most ${\log n}$ . Then, ${M_{[i,c]}}$ on all ${y}$ of length ${n}$ is correct, since

$\displaystyle y \le 2^{n} = 2^{2^{|i|+c-1}} < f(i,c).$

The size of the circuit that simulates this Turing machine on inputs of length ${n}$ is polynomial in ${|i|}$ , ${n}$ , and the running time of the machine. The machine, by definition, runs in time

$\displaystyle |y|^{c} \le n^{c} \le n^{\log n}.$

Thus, the theorem is proved. $\Box$

Open Problems

Before I state some open problems, I want to thank Subrahmanyam Kalyanasundaram and Ken Regan for many helpful comments on this post. Subrahmanyam has helped me many times, and is terrific at helping improve the posts.

Ken pointed out several interesting things that I will have to leave for a future post. The main issues he raised are: First, there is previous work on the “curious” property done by Shai Ben-David in an apparently unpublished 1992 technical report. Further, Ken also points out that any NP-complete language can be used in the place of ${\mathsf{SAT}}$ .

Second, that the placement of P=NP into AH has been thought about before–I am not surprised. Ken mentions that the logician Alex Wilkie repeated a rumor to the effect that P=NP was in $\Pi_1$ in a pub one of his publications in the mid-1980s, but nothing more ever came of it. Then, Ken recalls, that Tomoyuki Yamakami and others claimed this again around 2002-2003, but their claim was later withdrawn.

Finally, one of the reasons that a $\Pi_{2}$ sentence ${\forall x \, \exists y \, A(x,y)}$ can be unprovable in Peano Arithmetic is that the Skolem function for this sentence may grow too fast. This happens, for example, for the famous Paris-Harrington version of the Ramsey Theorem. So what the above theorem says is this: if P ${\neq}$ NP is unprovable in Peano because the Skolem function grows too fast, then my nightmare about P=NP happens. This is the core idea of the paper of Ben-David. More on his interesting work in a future post.