Andy's Math/CS page

Thursday, January 18, 2007


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

Labels: , ,


  • Hi, Nice problems!
    1) Given a circuit C(y), create another circuit C'(x,y) (x is n+1 bits) that does the following: C'(0^{n+1}, y) = 0 and for all other x, C'(x,y) = C(y). If the number of accepting paths is more than rejecting, then eventually they will overcome the 2^n headstart given to rejecting paths.

    2) Guess the value of z and ask the PP oracle to check if y satisfies.

    3) Contest is hard for NP^{PP}. Given a circuit C(x,y) create C' which does the following: C'(x0y) = C(x,y) and C'(x1y) = NOT C(x,y). So essentially we are making sure that, for consecutive x0y, x1y the number of accepting and rejecting paths become equal.

    Keep Posting!

    By Blogger Prasad, at 11:14 PM  

  • Hi, Prasad! You've got the right ideas; however, two comments:

    a) the solution to 3) needs to use as subroutine the transformation you described in 1). Your solution to 3) shows how that the class I would call 'NP(CONTEST)' is equal to the class whose complete problem is CONTEST, but first you need to reduce NP(PP) to NP(CONTEST) via the idea of 1). Let me know if this is unclear.

    b) NP(PP), i.e. the class defined as the set of languages poly-time many-one reducibile to the complete problem I mentioned for it,

    is (probably) NOT equal to
    NP^{PP}. If we were to give a computational model for NP(PP), the nondeterministic machine would get to make only one PP query per computation branch, and the bit it received would have to be its own output. In NP^{PP}, by contrast, the nondeterministic machine gets to make polynomially many adaptive PP queries.

    PP does have some pretty strong known closure properties, but not as strong as showing

    Thanks for your interest, and refer to the Complexity Zoo for more info/references on PP.

    By Anonymous Andy, at 8:01 PM  

  • Thanks for the comments! I had overlooked the distinction between NP{PP} and NP^{PP}.

    By Blogger Prasad, at 5:27 AM  

  • No problem. The general idea for classes like NP(PP) is that they are a result of applying the 'NP operator' NP(*) to the class PP, in the sense you'd expect from this example. There is also a 'PP operator', etc. Generally A(B) is weaker than A^{B}. (I believe Uwe Schoning invented these things, but could be wrong. Anyways, they're discussed in his 'Gems of TCS' book, and in the book 'Structural Complexity Theory' by Balcazar et al.)

    Question: which is more powerful, PP(NP) or NP(PP)?

    By Blogger Andy D, at 12:56 AM  

  • I don't know the answer, by the way, and I'm too fried to think about it right now.

    By Blogger Andy D, at 12:58 AM  

  • PP(NP) = PP

    By Anonymous Rahul, at 10:59 PM  

  • This comment has been removed by the author.

    By Blogger Andy D, at 2:00 PM  

  • Rahul--thanks. I don't see why that is so, but I'll think about it. I do know how to show PP^{FewP} = PP.

    I can answer my question in a different way:

    PP(NP) \subseteq PP^{NP} \subseteq PP^{PH}

    \subseteq P^{PP}

    (the last is a strengthened form of Toda's Theorem; see 'The Complexity Theory Companion', Chap. 4)

    \subseteq NP^{PP},

    and NP^{PP} *equals* NP(PP), contrary to what I said to Prasad. This is a consequence of the fact (which can also be distilled from CTC Chap. 9) that PP has polynomial-sized conjunctive self-reductions; i.e., given a language L in PP, there is an algorithm M that, given a list s_1, ... s_n of strings, produces a string u such that

    u is in L iff
    all of s_1, ... s_n are all in L.

    Moreover M runs in time
    poly(|s_1| + ... |s_n|).

    By Blogger Andy D, at 2:03 PM  

  • Needless to say, my solution to the previous question is exactly what the solution of a puzzle should NOT look like: a rote use of powerful, esoteric results from the literature. But hopefully there's a self-contained proof somewhere that'd make a proper puzzle of it.

    By Blogger Andy D, at 4:50 PM  

  • Andy, you're right, the simulation I was thinking of only works for PP^FewP. Ought to have thought about it longer...

    By Anonymous Rahul, at 10:38 PM  

  • Hey! Coach Factory Online simply wanted to say your website is one of the nicely laid out, most inspirational I have come across in quite a while.

    By Anonymous Coach Factory Online, at 2:49 AM  

Post a Comment

<< Home