An approach to independence with more complexity dependence

Florian Pelupessy recently defended his PhD thesis at the University of Ghent in Belgium. In joint work with Harvey Friedman, he found new short proofs for two independence results from Peano Arithmetic. One result is the famous “natural” Ramsey-theoretic independence result proved by Jeff Paris and Leo Harrington in 1977, while the other is a different Ramsey-type result obtained in 2010 by Friedman. Pelupessy also maintains a page with links on “phase transitions” in proof theory—meaning cases where a slight change in values of parameters makes a statement go from being provable to independent.

Today I want to talk about whether we can prove that some of our open problems are independent of Peano Arithmetic or other theories.

When we cannot prove something several ideas come to mind. Perhaps it is false, or perhaps it is time to try and prove the opposite statement. Or perhaps it is time to move on and try to work on some other problem. Or perhaps the reason we have failed to solve the problem is that it is actually unprovable. Kurt Gödel’s famous Incompleteness Theorem shows, roughly, that any powerful enough theory must either be inconsistent or incomplete.

That is the theory must either prove everything—it is inconsistent—or it must miss proving some true statements. One idea that keeps coming up, one question that we hear often is: could our favorite open problems like ${\mathsf{P}=\mathsf{NP}}$ be unproved, since there are no proofs? It’s hard to find a needle that is not in the haystack.

We have talked about independence before—here—but I wanted to add some new thoughts on this issue.

An Independence “General Nonsense”

Ken and I were both part of a bunch of people interested three decades ago in whether a general kind of independence result had larger significance. The general idea is that there are computable functions ${f(x)}$ that outgrow every function that Peano Arithmetic can prove to be total. Moreover, one can majorize them in a sense by predicates that are very easy to compute:

Theorem: For every computable ${f(x)}$ we can compute a function ${g(x)}$ such that:

1. ${g(x)}$ is computable in linear time and log space;

2. for every ${y}$ there are infinitely many ${x}$ such that ${g(x) = y}$;

3. the function ${h}$ mapping ${x}$ to the least ${x' > x}$ such that ${g(x') \neq g(x)}$ makes ${h(x) > f(x)}$ infinitely often; and

4. for all ${x}$, ${h(h(x)) > f(x)}$.

Indeed Ken’s 1996 paper with Heribert Vollmer showed how to compute ${g}$ in various notions of logarithmic time. Think of the values ${y}$ as being “colors”: red, green, blue… Then ${g}$ colors ${\mathbb{N}}$ with infinitely many colors, but such that each one of the following false statements is consistent with Peano:

1. The range of ${g}$ is almost all red.

2. The range of ${g}$ is almost all green.

3. The range of ${g}$ is almost all blue.

4. ${\;\;\;\;\dots}$

To apply this, make a language ${E}$ that consistes of the red strings in ${\mathsf{SAT}}$, the green prime numbers, and the blue strings that belong to the Graph Isomorphism language. Then since all these languages belong to ${\mathsf{NP}}$ and ${g}$ is easy, ${E}$ belongs to ${\mathsf{NP}}$. However, it is consistent with Peano to believe that ${E}$ is a finite difference of any one of these languages. If in fact ${\mathsf{NP \neq P}}$, then it tumbles out that ${E}$ is neither in ${\mathsf{P}}$ nor ${\mathsf{NP}}$-complete, and not polynomial-time equivalent to Graph Isomorphism either. Hence all of these facts are independent. This applies regardless of what machine code is used to specify ${E}$ formally. One can churn out myriad similar instances.

This kind of theorem once seemed exciting, but has proved unsatisfying, because it doesn’t really say much about complexity. So here we want to think of ideas that are more concrete about computations.

The BPP Hierarchy Problem

Call a nondeterministic Turing Machine (NTM) decisive provided on an input either at least ${2/3}$ paths accept or at least ${2/3}$ of the paths reject. We assume in these machines that all paths have the same length with binary branching. That is, they have the same probability if the NTM is viewed as a randomized Turing machine.

The complexity class ${\mathsf{BPTIME}(T(n))}$ contains those languages accepted by a decisive NTM that runs in time ${T(n)}$. The classic open problem is: does more time help for these complexity classes? More precisely is

$\displaystyle \mathsf{BPTIME}(n^{k}) \subsetneq \mathsf{BPTIME}(n^{k+1}),$

for any ${k \ge 1}$? This is widely believed to be true, but is open even in the oracle world. See the last section of this post for a summary on this.

An Idea

I have often thought about trying to prove something like the following. There is a language ${L}$ so that ${L}$ is not in ${\mathsf{BPTIME}(n)}$, and yet it is consistent with Peano Arithmetic (PA) to suppose that ${L}$ is in ${\mathsf{BPTIME}(n^{2})}$. This is plausible, and stays “safely” short of proving what we really want. Still even this seems difficult.

I would like to share an idea about how one might attack this problem. To make the explanation “fun,” let’s call an NTM program ${N}$ a Knight if it is decisive and runs in at most linear time; let’s call ${N}$ a Knave if it runs also in linear time but is only stipulated to be decisive for inputs of length ${n \le f(N)}$. It can be decisive elsewhere, but must be decisive for these length inputs. Here ${f}$ is the computable function mentioned above that Peano Arithmetic cannot prove to be recursive, or even bounded by a recursive function. So a Knave can look like a Knight for many inputs.

Let ${M}$ be a NTM that runs always in time ${n^{2}}$. It operates as follows. On input ${x = \langle N,0^{w}\rangle}$ it does the following: It checks that ${w > 2^{f(N)}}$. If not then it rejects. If it is true, then we check that ${N}$ is decisive on all inputs of length at most ${f(N)}$. If it fails, then again we reject. But if it works, then it simulates ${N}$ on the input ${x}$ for ${n\log n}$ steps and flips the answer.

Let ${L=L(M)}$ be the language accepted. We claim that ${L}$ is not in ${\mathsf{BPTIME}(n)}$. This follows since we diagonalize over both Knights and Knaves.

What can we say about ${L}$ being in ${\mathsf{BPTIME}(n^{2})}$? The time bound is not a problem. The problem is whether there is a decisive machine that accepts ${L}$. In order to study this consider the formal sentence:

What this says is that there are an infinite total recursive number of inputs that make ${M}$ indecisive. Note that if this is false, then ${M}$ is decisive for all but a finite set of inputs. Since ${\mathsf{BPTIME}(n^{2})}$, like most complexity classes, is closed under finite differences of its languages, falseness implies that ${L}$ is in ${\mathsf{BPTIME}(n^{2})}$.

The critical idea is that I believe, but cannot prove, that this sentence is consistent with PA. The intuition is that provided ${f()}$ grows very fast, if PA could find an infinite number of bad inputs, then this would contradict the growth of ${f}$.

I must admit this seems close, but it does not yet work. Perhaps someone can fix the above argument.

Open Problems

Can the above argument be made to work, and yield more interesting independent statements?

Ken suggests a problem that may be a stepping-stone. Define ${\mathsf{Q}}$ to be the class of languages accepted by polynomial-time NTMs ${N}$ such that for some poly-time NTM ${N'}$, Peano can prove that ${L(N)}$ and ${L(N')}$ are complements. Then ${\mathsf{Q} \subseteq \mathsf{NP} \cap \mathsf{co}\text{-}\mathsf{NP}}$, and by enumerating proofs, we can construct a language ${B}$ in ${\mathsf{NP} \cap \mathsf{co}\text{-}\mathsf{NP}}$ to which every language in ${\mathsf{Q}}$ reduces.

This is cool: if every language in ${\mathsf{NP} \cap \mathsf{co}\text{-}\mathsf{NP}}$ is provably so, then ${\mathsf{NP} \cap \mathsf{co}\text{-}\mathsf{NP}}$ has a complete set. The question is, does ${\mathsf{Q}}$ itself have a complete set, regardless? The hitch with ${B}$ is that proving a nontrivial ${N'}$ accepts the complement of ${B}$ seems to involve proving that Peano is consistent, which Peano itself cannot do. But perhaps a coding trick can construct a ${B'}$, and importantly a formal sentence representing it, which can be proved while avoiding a fatal self-reference.

1. April 24, 2013 4:37 pm

“any powerful enough consistent theory must either be inconsistent or incomplete.”

I think we can safely rule out the first possibility.

• April 24, 2013 8:29 pm

Whoops—my bad. As editor I started simplifying Dick’s original sentence to be “any powerful enough consistent theory must be incomplete” until seeing below that Dick had a reason to write it as he did. Fixed.

2. April 24, 2013 11:50 pm

Assuming that the above sentence L can be expressed arithmetically, in a paper (link below) presented at AISB/IACAP 2012, Birmingham, I define an algorithmic model of the first order Peano Arithmetic PA, over the domain N of the natural numbers, in which the above sentence would interpret as:

‘There is an algorithm which can decide that, for any given natural number x, it is not the case that there is an algorithm which can decide that, for any given natural number y, the machine M is not decisive on input y.’

Prima facie we cannot therefore assume (without inviting inconsistency) that L can be taken as expressing the following assertion in PA:

‘There are an infinite total recursive number of inputs that make M indecisive.’

Paper: Evidence-Based Interpretations of PA

Regards,

Bhup

April 26, 2013 8:09 am

“No-Go theorems” generally are repugnant to our aesthetic sensibilities, and eminent scholars who have endorsed this principle include Bertrand Russell “It is one of the chief merits of proofs that they instill a certain skepticism about the result proved” (1903), Henry George Forder “The virtue of a logical proof is not that it compels belief but that it suggests doubts” (1927), and Morris Kline “The virtue of a logical proof is not that it compels belief but that it suggests doubts” (1982).

Fortunately, complexity theory literature — notably Juris Hartmanis’ monograph Feasible Computations and Provable Complexity Properties (1978) — inspires us to associate positive theorems to the great open questions of complexity theory. Here is an example, that is distilled more-or-less directly from Hartmanis’ own writings:

The Little PvNP Postulate  Let P’ and NP’ be the set of languages in P and NP (resp.) for which ZFC provides certificates of membership. Then ZFC suffices to prove three more strict inclusions: P’ ⊂ P, NP’ ⊂ NP, and P’ ⊂ NP’.

Needless to say, if we believe that P ⊂ NP is a strict inclusion, then almost certainly we believe that P’ ⊂ NP’ is a strict inclusion too! So how hard can it be, to prove a theorem that we know (in your heart!) is true, and whose assumptions severely constrain the domain of the complexity classes involved? 😉

A striking testimony to the narrowness of 20th century conceptions of complexity theory, is that a proof of the Little PvNP Postulate would not win the Clay Institute’s Millennium Prize for “solving” the P versus NP problem … even though a Little PvNP Theorem likely would require more innovations in its proof methodology, and arguably would be deeper in its implications, than any of the (purely technical) PvNP proof strategies that have been advocated in the literature.

Conclusion  Nature generously provides plenty of “burning arrows” — see this, this, and this prior GLL essay for further examples of “burning arrows” — with which hopeful 21st century researchers can attack the fortress of PvNP! Good!

April 26, 2013 4:31 pm

Whoops … the Morris Kline quote should have been “The proof tells us where to concentrate our doubts.” Kudos to Bertrand Russell for being (apparently?) the first mathematician (as of 1903) to voice this heuristic strategy for conceiving “burning arrow” proof methods.

4. May 6, 2013 7:41 pm

“The Little PvNP Postulate Let P’ and NP’ be the set of languages in P and NP (resp.) for which ZFC provides certificates of membership. Then ZFC suffices to prove three more strict inclusions: P’ ⊂ P, NP’ ⊂ NP, and P’ ⊂ NP’.”

Let the above assertion be B.

THEOREM. B holds if and only if ZFC is inconsistent. In fact, this equivalence can be proved in a weak fragment of finite mathematics. Thus B has nothing to do with complexity theory, and is normally judged to be extremely unlikely, if not absurd.

Proof: Suppose B holds. Any of these displayed strict set inclusions immediately implies that ZFC is consistent. Because if ZFC is inconsistent, then set equality holds because ZFC proves everything. Hence (from B we have) ZFC proves ZFC is consistent. By Goedel’s second incompleteness theorem, ZFC is inconsistent. This establishes the forward direction. Conversely, suppose ZFC is inconsistent. Then ZFC proves anything, and so B holds. QED

The statement B can be weakened to B’ by weakening the first ZFC to, say, PA, and leaving the second ZFC alone. But now one can put a timer on the TM’s and show that the three set equalities hold, demonstrably in ZFC. Thus we obtain the same Theorem for B’.

I would be surprised if this is what Hartmanis had in mind.

Harvey Friedman