News, and some Number Theory

Time for a personal update: I'm enjoying myself greatly here in Cambridge, and was recently admitted as a transfer student to MIT's EECS department. The move has both personal and academic advantages for me, but let me emphasize that I think UCSD has a lot to offer prospective students, and in addition is home to many cool people whom I miss... I would be happy to offer advice about either school.

When I started writing here as an undergrad, I knew very few people in the worlds of TCS and Complexity, and the blog was a way of reaching out to a community I wanted to join. Now, thanks in part to blogging (thru which I met Scott, my advisor), I'm immersed in that community at a school with a large, vibrant Theory group. This is to say that, though writing here still interests me, it no longer answers an urgent personal need, and I am most likely to post new material in response to a request for specific topics or post types.


Today I was perusing a favorite book of mine, 'Gems of Theoretical Computer Science' by U. Schoning & R. Pruim. One chapter partially treats the undecidability of determining whether systems of Diophantine equations (polynomial equations where solutions are required to be integral) have a solution. This was one of Hilbert's problems from 1900, solved in 1971 and full of deep math.

The authors pose the following exercise: show that the version where variables must take nonnegative values, is reducible to the integer version. (And vice-versa; also the rational-values version is reducible to the integral version; the converse appears to be open...)

Think about it...



The reduction they give: Given a set of polynomial equations {P_i(X_1, ... X_k)}, we want to determine if they're simultaneously satisfiable with nonnegative values. Introduce, for each j <= k, the variables Y_{j, 1}, Y_{j, 2}, Y_{j, 3}, Y_{j_4}.

Now add to the system, for each j <= k, the constraint that

X_j = Y_{j, 1}^2 + Y_{j, 2}^2 + Y_{j, 3}^2 + Y_{j_4}^2.

Claim: the new system is satisfiable over the integers iff the original one is satisfiable over the nonnegative integers! The proof, of course, is an easy consequence of Lagrange's Theorem that every nonnegative integer is the sum of 4 integer squares.

So, my question is, could a reduction be found that doesn't rely on Lagrange's Theorem? Or its weaker variants where the constant 4 is replaced with some constant c > 4. Or maybe for some constant c, the proof is really so simple that I will be satisfied that we are performing this reduction with the cheapest tools.

If our plan in the reduction is to constrain the original variables in a form analogous to the above, namely

X_j = Q_j(Y, Z, ...),

where Y, Z, ... are new integral variables, is there any way around proving a version of Lagrange's Theorem? Generally we show that polynomials are identically nonnegative by expressing them as a sum of one or more squares, e.g.,

Y^2 + Z^2 - 2YZ = (Y - Z)^2.

Using this template, we'd be reliant on Lagrange. However, in his thesis, Minkowski conjectured that there exist nonnegative real polynomials *not* so expressible, and this was proved by Hilbert. A simple example I found online is

Q(X, Y, Z) = X^4*Y^2 + Y^4*Z^2 + Z^4*Y^2 - 3X^2*Y^2*Z^2,

and another counterexample is derived systematically in the classy and useful inequalities book 'The Cauchy-Schwartz Master Class' by J.M. Steele. (Artin proved, however, that every poly that's identically nonnegative, is expressible as the sum of finitely many *rational* functions squared.)

Could it be that one of these creatures is easier to use in the reduction (both to prove it's nonnegative, and ranges over all nonnegative values)? Somehow I doubt it. Anyways, I just wanted to point to an instance where a reduction one would expect to be straightforward seems to require fairly nontrivial understanding of the problem domain.

Dogs in the Mineshaft

A couple posts ago I described some shenanigans with cats in a binary tree.
But that was just the front yard. The back yard is worse: it contains the opening of an old mineshaft that descends infinitely far into the earth's depths.

Well, there's some funky smell down there that dogs just have to investigate. So, every day, some finite number of dogs may enter or go further down the (unbranching) shaft. They never go back upwards. Here's the scene:



As before, you've got angry owners on your hands. You refuse to close off the shaft (it's too nifty) but again you're willing to try and ensure that any individual dog descends only finitely far into the shaft. Your tool this time: it turns out that after enjoying a good steak, a dog will curl up and fall asleep indefinitely.

The difficulty is that, before eating any steak you give it, the dog may carry it arbitrarily far further down the tunnel. If it passes sleeping dogs, they may be awakened by the steak aroma, and resume their descent.

Money, time, and steaks are no object, and you can outrun the dogs, who won't smell the steaks if they're sealed in your coat pocket. Can you keep your promise to the owners?

To get you started, consider a simple but unsuccessful strategy of giving a steak to every dog every day. The problem is that some dog D may have a sequence of 'accomplice' dogs: every time D falls asleep, a new accomplice will run into the tunnel and hang out above D in the shaft. When you give the accomplice a steak, it'll scamper past D, who'll rouse and go further. In fact, it may happen that every dog goes infinitely far down the tunnel!

Another simple idea is to give a steak every day to the dog furthest down the tunnel, if that dog is not already asleep. This avoids ever waking up sleeping dogs (assuming that the previous day's steak has had its effect; if not we can just wait longer), but it falls victim to a 'rear-guard' attack: a dog that trails constantly just above/behind the current leader.

***

This is a challenging puzzle (unless there's a glitch in the set-up, which I've checked over). But it's well worth thinking about, because the solution strategy--the 'finite injury' or 'priority' method of Friedberg and Muchnik--revolutionized computability theory. Some would say it marked the end of its comprehensibility to outside observers, but I'm optimistic that is not the case. The ingenious strategy is lovely, simple, and, fingers crossed, easier to see in a puzzle setting. I will discuss the solution in a future post, so stay tuned.

Update: Scratch that, Gareth Rees has solved the puzzle and clearly explained the solution for us, in the comments section of 'Trees and Infinity, part III'. I may still talk more in the future about its significance to computability.

Trees and Infinity, part III

(Hat tip to Gareth--my first fan art!)

Today, a computability theory-inspired quickie puzzle. Can you face down the infinite in its many guises?

Cats in a Tree

Some GMO-contaminated sludge washed onto your property during the latest freak weather event. A few weeks later, a mysterious tree has sprouted on the lawn, and its progress is astounding--every day, a new layer of binary growth appears:



This would be peachy, but there's a problem: your neighborhood suffers from a plague of cats. Mangy, poorly drawn, tree-climbing cats:



On any given day, some (finite) number of cats may start climbing the tree, or continue their climb from a previous day. What they don't know how to do is come down, not even a single level.
The cats all have irate, protective owners. They want you to cut down this cat sinkhole at once (after rescuing their pets). But you're not going for that--you want the world's largest tree, with unending growth.

Here's the compromise you'd like to offer the owners: a guarantee that every cat C will eventually be prevented from climbing above some level n (which may depend on C).

To achieve this, you have the following means: on any day, you can climb to any number of nodes of the tree and strip the bark there, preventing further growth above the stripped nodes.
Of course, stripping the root node would stop the cats. The challenge, again, is to achieve unending growth as well (though not necessarily the full binary tree).

Good luck!



***

This puzzle models the theorem that there exists an infinite recursive tree with no infinite recursive path. (Interestingly, however, no recursive tree T can have the Halting problem computable with the aid of an arbitrarily chosen infinite path from T. Promise problems are subtle...)

Can the whole theory of computability be 'sweetened up' this way, like the Flintstones vitamins I gobbled up in my youth? Here's a proposal: once students understand programs' capacity to simulate other programs and other computational models, dovetail search procedures, and other 'infrastructural' techniques, it may be preferable to actively 'forget' the computational statement of a problem one aims to prove.
So, in the above puzzle, the cats correspond to different simulated programs in an enumeration, but we are so profoundly unable to predict in advance the behavior of these programs that it might be better to think of the situation adversarially--hence, mischievous cats who do just as they please.
Of course, one could also make a case for the aid to visualization, and possibly generalization, given by the metaphoric puzzle format, but here I mean specifically to ask whether metaphors might help students develop a stronger familiarity with the black-box methodology of computer science.

Next time: the Finite Injury method!

PPuzzle

Today I'd like to present an exercise about PP and related complexity classes, requiring only basic familiarity with reductions in complexity theory. The result involved has almost certainly been discovered before, and I'd appreciate any references.

But first, why do I present so many exercises and puzzles? It's not just to skimp on exposition; it's because, for me anyway, doing puzzles is a joyful activity and the best way to really learn a field. When I pose a puzzle, you have my promise that the solution is both interesting and not too complicated, unless I say otherwise. I will give a sense of the basic background you need, so e.g. I won't ask you to reinvent the probabilistic method (as Kuhn says, puzzles are within and relative to a paradigm, whatever that means).

If theoretical computer science wants to compete with other areas of math in enticing and effectively training young problem-solvers, it needs to have a better sense of what its puzzles are. I hope to say more about this soon.


Here is a computational problem, which I'll call CONTEST:

**********************************************
GIVEN: A boolean circuit C on n input bits, outputting a single bit;

DECIDE: is there a z in {0, 1}^n such that at least half of the outputs {C(y): y <= z in the lexicographic ordering} are 1's?
**********************************************

In other words (and supposing for illustration n = 4), if the outputs {C(0000), C(0001), C(0010), ... C(1111)} give votes for candidates 0 and 1, in the order in which they were received, was candidate 1 ever ahead or tied in the running tally? (i.e., does candidate 1 make a 'contest' of it?)


Problem 1: Show that CONTEST is hard for PP, whose standard complete problem is the following:

**********************************************
GIVEN: A boolean circuit C(x) on n input bits, outputting a single bit;

DECIDE: Are at least half of C's outputs 1's?
**********************************************

Problem 2: Show that CONTEST is in the class NP*(PP), whose standard complete problem is the following problem:

**********************************************
GIVEN: A boolean circuit C(x, y) on 2n input bits (|x| = |y| = n), outputting a single bit;

DECIDE: is there an x in {0, 1}^n such that at least half of the outputs {C(x, y): |y| = n } are 1's?
**********************************************

Problem 3: CONTEST is complete for either PP or NP(PP); which one?
The proof is simple and, I think, amusing.

For those who've been bit by the computability bug (as I've been recently, witness some previous posts), there are many related problems:

GIVEN: A polynomial-time machine M outputting 0's and 1's, viewed as a sequence.

DECIDE: a) Do 1's ever outnumber 0's in an initial segment of the sequence?

b) Do 1's outnumber 0's infinitely often?

c) Does the sequence a_n = (number of 1's up to length n ) - (number of 0's up to length n) diverge properly to positive infinity?

These decision problems are listed in increasing order of unsolvability, and their exact complexity can be pretty readily determined using the k-round game characterization of level k of the Arithmetic Hierarchy that I mentioned in the post 'Trees and Infinity II'.

Trees and Infinity, part II

Previous: Part I




Next: Part III



Time for another short installment on trees and recursive combinatorics, that will address a question raised by the previous puzzle and take us on an journey beyond the arithmetic hierarchy (cue your favorite sci-fi theme music...).

To recap, Konig's Lemma guarantees that a locally-finite infinite tree has an infinite path.

Suppose some machine M(x) computes membership of x in a locally-finite tree T; if x is in T then M(x) outputs the parent and immediate children of x. Then there is no guarantee that T has a computably-describable infinite path; however, such a path can be computed, uniformly in M (assuming we know the root node), given oracle access to the Halting set.

Konig's Lemma fails if the nodes can be infinite-degree, even if the tree is infinite at every height (Exercise). But consider the following computational problem:

INF: Given a Turing machine M describing a tree T (not necessarily locally finite), does T have an infinite path?

This question has a superficial simplicity: it is purely existential. However, the object it seeks is infinite, and unlike in the case where Konig's Lemma applied, there is no obvious finite 'no' certificate. Here's the astounding truth of the matter:

Problem 1: There exists an algorithm which, given any formula F of first-order logic, outputs a polynomial-time Turing machine M describing a tree T such that T has an infinite path if and only if F is true.

Solving the problem boils down to this: suppose we've got a statement of the form Q: "there exists a number x such that P(x) is true", and we know how to convert each individual P(i) to a tree that has an infinite path if and only if P(i) is true; we now need to use this knowledge to build a tree corresponding to Q.

Only slightly harder is the other case that arises: if Q is of form "for all numbers x, P(x) is true", where we again know how to build trees for each individual P(i). Still, this is pretty cool, since you are effectively reducing a universal condition into an existential one. Once you can handle both cases, you can systematically attack an arbitrary first-order expression.

***Interlude: A Review***

If you're not up on first-order logic, just consider F a statement of form

"the game G(X1, X2, ... Xk) is a win for player 1 (assuming perfect play)",

where G is a computable function from N^k --> {0, 1} that defines a game as follows: player 1 and player 2 take turns in choosing values the k values X1, X2, ... Xk, and player 1 wins if and only if G evaluates to 1 under the input chosen.

This 'computable game' formulation turns out to be equivalent to first-order logic; i.e., given any F we can produce a G such that G is a win for player 1 if and only if F is true, and the number of play-rounds of G equals the depth of alternating quantifiers in F; there is also a reduction in the reverse direction.

***

So how hard is the computational problem of checking for infinite paths? If I've got my definitions right, it's complete for the first level of the analytic hierarchy: existential second-order logic.

Now here's a tie-in to the 'censor puzzle' I discussed recently. Given a 'classification' C of finite words over {0, 1} as allowed or forbidden and an infinite 'text' bitstring D, both poly-time computable, let PARSE be the computational problem of determining whether D can be parsed so as to appear wholly allowed with respect to C.

Problem 2: Show that PARSE and INF are Turing-equivalent.

The challenge in reducing INF to PARSE, which is not too hard to overcome, is that because our alphabet is finite, the same words pop up again and again, so our decisions in building up C keep on bugging us, whereas we want continual freedom of movement in encoding new and higher levels of the tree we are attempting to model in a PARSE instance.

In the reduction I came up with, it's always easy to find a wholly-forbidden parsing of the text string. Thus, as an open problem (update: solved! In the negative. See discussion in comments of Part I.) I ask,

Problem 3: Exhibit a PARSE instance, such that any parsing that is either wholly-allowed or wholly-forbidden (with the possible exception of the first word in each case) is not describable in the arithmetic hierarchy.


Conclusion

NP-completeness theory has transformed the way we regard finite optimization problems.
NP-complete problems require hard search, but on a basic level it's 'the same' hard search
in all cases.

Perhaps less widely known is that a similar phenomenon pervades higher
mathematics. Of course, computer scientists know that most natural
undecidable problems are so because they can be used
to solve the halting problem. If they are much harder (as with PARSE),
they are still likely to have a natural classification using the analytic
hierarchy or some other 'mega'-complexity class.

But there is more. If a highly nonconstructive proof seems to require
the axiom of choice, chances are the theorem being proved also
constructively implies some version of the axiom of choice and can be
classified as 'complete' for a certain logical class. This is a theme
explored by 'reverse mathematics', an area I'm only beginning to
learn about.

Revisiting familiar theorems with a view towards establishing their
complexity, informational, or logical content lends them new grandeur
and enriches our sense of the interconnectedness of the mathematical world.

Trees and Infinity

With this post I hope to do a little to strengthen readers' (and my) understanding of the mathematics of the infinite (something easy to neglect in the study of resource-bounded computation), while focusing on the discrete infinite structures that arise in computability theory.

In mathematics, a tree is an important kind of structure. It consists of a set of nodes, with one designated the root. Each node has a (possibly empty) set of 'children' (of which it is the parent), and any node is reachable from the root in a unique way by a finite series of steps, where each step takes you from a node to one of its children.

The genealogies of asexual organisms, for example, are naturally describable using trees. An important tree in discrete math is that formed with the finite bitstrings as nodes, where the root is the empty string and where the children of x are x0 and x1. (Exercise: use this tree to exhibit the following, somewhat startling, phenomenon: there exists an uncountable collection of subsets of N, the natural numbers, such that any two subsets have at most a finite intersection.)

This tree on bitstrings is an infinite tree, but it has the nice property of being 'locally finite': every node has only finitely many children. Konig's Lemma (the 'o' in Konig needs an umlaut) asserts that any infinite, locally finite tree contains an infinite path (hopping parent-to-child at each step).

The proof is simple: we build such a path. Start at the root; by the pigeonhole principle, one of the root's children c must itself be the root of an infinite subtree. Hop to c, repeat the same process, ad infinitum.
QED.

This innocuous Lemma is in fact very powerful. I will describe some basic applications.

1) The Compactness Theorem for Propositional Logic: Suppose {F_i} is an infinite family of Boolean functions over x_1, x_2, ..., such that i) each F_i depends on finitely many variables, ii) for each K we can find a setting of the variables that satisfies F_1, F_2, ... F_k (i.e. makes them all equal 1).
Then we can find an assignment satisfying all the F_i simultaneously.

Proof: For any finite bitstring y, say of length j, interpret y as an assignment to x_1, ... x_j. Say y is in T if there is no particular F_i that y has already forced to output 0.

T is clearly a tree, and locally finite. If it has an infinite path, that path describes an assignment satisfying all of {F_i}. So assume it does not. But then, by the contrapositive form of Konig's Lemma, T must be finite, say with no node representing a bitstring of length K or more.

This means that for any length-K bitstring y, there is some formula F_{i[y]} forced to be 0 by setting x_1 ... x_K = y.

How, then, can one find any assignment to x_1, x_2, ... that satisfies all of the finite set of formulas {F_{i[y]}: |y| = K } ? One cannot. This contradicts the assumptions of the Theorem, completing the proof.
QED.

Here's a nice application of the Compactness Theorem:

2) show that the 4-color Theorem of graph theory holds even for infinite planar graphs, as long as each graph node is of finite degree. (Assume the finite 4-color Theorem is valid. Or, hey, don't...)

Konig's Lemma or The Compactness Theorem can each yield a simple proof (exercise!) of the following 'query complexity'-type result:

3) Suppose f is a Boolean function on x = x_1, x_2, ... Say whenever f(x) = b, for b = 0 or 1, there is a finite subset of the variables which force f to equal b.
Then f in fact only depends on finitely many variables.

This result is redolent of the statement 'REC = RE intersect coRE' in computability. It also has an analogue in a more finite setting--a kind of moral equivalent of 'P = NP intersect coNP' in query complexity--which I invite readers to discover or ask about.

It's interesting to wonder to what extent Konig's Lemma can be 'constructivized'. Let D be an infinite subtree of the prefix-tree over finite strings (as described above). Suppose membership in D is computable. Say infinite string s refines D if all of its finite prefixes are in D.

4) Is it necessarily the case that for such D there is a computable s refining D? (Hint: Diagonalize.)

4.5) If the sequence of functions from the Compactness Theorem (1) is a computable one, is there a computable assignment to x_1, x_2, ... satisfying every function?

5) What if, in 4, there is an additional guarantee that only countably many s refine D?

For readers interested in Kolmogorov complexity, the following somewhat challenging result rewards similar tree thinking:

6) Suppose that for some infinite string s there is a constant C such that for all n, there is a Turing machine M_n which, on input n, outputs the length-n prefix of s.
Then s is computable. (The converse is easy.)
(Source for 6: the gorgeous Li-Vitanyi book on Kolmogorov complexity.)

Addendum: I just found a good source for further material related to 4-5 and other aspects of 'recursive (infinite) combinatorics': Bill Gasarch's chapter in the hefty Handbook of Recursive Mathematics, Vol. II.

Shifting quite a bit now, I'd like to briefly describe a nice probabilistic result about infinite genealogical trees. Consider an idealized asexual organism in an idealized environment. Each individual alive at time t (an integer) gives birth to some number (possibly zero) of offspring, whose number is determined by the outcome of a random variable X. Then the individual dies as we enter time t+1. Each new individual's reproduction is governed by the outcome of an independent copy of X (so, just because your parent had reproductive success doesn't make you more likely to).

X could be very complicated. But it turns out that the expectation E(X) is still quite powerful in understanding the population dynamics: if E(X) is less than 1 then an eventual extinction occurs with probability 1, while if E(X) is greater than 1 then extinction happens with probability less then 1, and conditioning on the event that extinction does not occur, then with probability 1 the population size goes to infinity rather than oscillating indefinitely.
The proofs I've seen of these results are generatingfunctionological. Are there more 'natural' proofs out there? Or a relation to Konig's Lemma?


I should note that real trees are worth thinking about too. I would recommend the site Carbonfund.org as what seems to be the most well-run and cost-effective place to buy carbon credits, reducing global warming and deforestation. $55 will offset 10 tons of CO2, a significant chunk of the direct yearly impact of an average American.
P.S. Anyone who uses PayPal for this kind of thing should be aware of the fraudulent emails sent by PayPal impersonators to solicit credit card numbers.

Finally, for a more soulful/whimsical take on trees and the infinite you might check out Calvino's novel The Baron in the Trees. (Thanks, Chaya!)

Fast but Useless

My thesis is about hard functions that are useless. But there's a natural structural condition on functions that makes them useful (and hard): they grow faster than Busy Beaver. In such cases they can act as a timer to solve the halting problem. Is this the end of the story?

A while ago Scott Aaronson mentioned the following question to me while discussing questions around my thesis and a post of his: is there a function asymptotically dominating all recursive functions that *doesn't* allow you to solve the halting problem? He said he'd asked Carl Jokusch, who gave a 'high-powered' proof. I found an easy proof that proved something stronger:

Theorem: Let RAND be the Kolmogorov-random strings; then there's a function f dominating all recursive functions such that RAND is 'immune' (one can't compute an infinite subset of it) even given oracle access to f.

(HALT is Turing reducible to RAND--even truth-table reducible, which is bizarre--so it follows that HALT is not Turing reducible to f. Actually, the theorem remains true if you replace RAND with any immune set.)

Proof: Let B[1](x), B[2](x), ... be a (nonconstructive) enumeration of all total recursive bounds. At each stage we set finitely many values of f to screw up the ith oracle machine M[i]'s attempt to decide an infinite RAND-subset. At stage i we restrict ourselves to setting new values f(x) >B[j](x) for j <= i; this gets the growth condition.

Case I: There's a finite partial completion of f, subject to the constraints/commitments so far, causing M[i] to accept some non-random string x.
Then of course, fix these f-values, along with a big value f(i) to ensure convergence of our partial f to a total function.

Case II: For no such partial completion can M[i] be so induced.
Then M[i] is not a problem: no matter how we set the function hereafter, M[i] can only accept a finite subset of RAND. Otherwise, we could code in the f-values committed so far along with programs for B[1](x), B[2](x), ... B[i](x) into oracle-free machine M', which on input x dovetails over all admissible partial completions of the oracle looking for one that makes M[i] accept x. Then M' accepts an infinite RAND subset, impossible.

So in Case II just fix a big value for f(i) to help
convergence. Continue over all i to get the desired f.

I've also explored a dual question (are there non-r.e.-hard infinite subsets of RAND?), with only partial success:

i) There is no algorithm that computes HALT when given oracle access to any infinite subset of RAND;
ii) There are infinite subsets of the 1/2-random strings (not compressible by a factor of two) that aren't r.e.-hard.

Happy to get questions or comments. Lance Fortnow and others have interesting results about the computational power of 'dense enough' subsets of 1/2-RAND.

Welcome!

Hi, my name is Andrew Drucker; I'm currently a senior undergraduate at
Swarthmore College. I've set up this page to make my thesis available
to graduate schools and to the public.

It's called 'Rich but Useless Information', and it represents independent research in Computability Theory. I hope you like it.. and if you're considering making a joke about the title, please consider that I might have heard it already.

Here it is:

Andy's Thesis

Thanks for your interest! I welcome questions and comments at adrucke1 (at) swarthmore.edu. Below, for quick reference, is a copy of the Abstract:

Abstract. We show the existence of an incomputable function f such that for any Turing machine M, when each input x to M is supplemented with 'advice' f(x), M cannot solve any incomputable decision problem. In fact, we strengthen this result in three ways: 1) the advice function can be constructed to have no recursive upper bound, 2) it can be made so as to hold fixed the class of recursively enumerable sets, 3) for any fixed recursive bound B(x), the advice function can be made so as to hold fixed the class of functions computable by machines with output bound B(x). We also examine the barriers (some methodological, some provable) to combining these results in a single construction.