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'.