Friday, September 23, 2011

Mahaney's Theorem

Bill has a lot of posts where he questions whether to teach Mahaney's theorem in a graduate complexity class. Since it is one of my favorite theorems and most of you young folk won't see a proof in your complexity classes, I'll give it here. This proof is not the original of Mahaney but based on a paper by Ogihara and Watanabe.

Mahaney's Theorem: Let c be a constant and A be set such that for all n, A has at most nc strings of length n. If A is NP-complete then P=NP.

Proof: We define the left-set of SAT as follows: Let B = { (φ,w) | φ has a satisfying assignment a with a ≤ w in lexicographic order}. We'll restrict ourselves to w that are (not necessary satisfying) assignments for φ.

Assume φ is satisfiable and let a' be the lexicographically smallest satisfying assignment. We have (φ,w) is in B iff w ≥ a'.

Since B is in NP by assumption B reduces to A via some function f computable in polynomial-time, (φ,w) is in B iff f(φ,w) is in A.

Fix φ and n and let m=nk bound the number of strings in A of any length that f(φ,w) could query. Pick w< w1 < w2 < … < wm+1 evenly spaced from each other.

Let zi = f(φ,wi) for each i. Note that if zi is in A then zj is also in A for all j ≥ i.

Case 1: zi = zfor some j > i. We know a' cannot be between wi and wj.

Case 2: All the zi are distinct. There are only m elements in A so z1 is not in A and a' cannot be between w0 and w1.

Either way we have eliminated a 1/(m+1) fraction of the possible assignments.

We repeat the process choosing the wi equally spaced among the remaining possibilities and eliminate another 1/(m+1) fraction of those assignments. We continue O(mn) times until we narrow down to a set S of m+1 possible assignments.

If φ is satisfiable then a' is in S so at least one assignment in S and will satisfy φ. If φ is not satisfiable then none of the assignments in S satisfy φ.

By trying all the assignments of S and seeing if they satisfy φ, we get a polynomial-time algorithm to determine if φ is satisfiable. Since Satisfiability is NP-complete we have P = NP.


  1. Lance (or anyone else): is there any argument to teach Mahaney's theorem (other than as a time filler)?

    As I understand it, Mahaney's theorem was interesting at the time because of its relation to the isomorphism conjecture. But Mahaney would have only really shed light on the conjecture if he had proven the opposite, and anyway most people now believe the isomorphism conjecture is false. So why teach Mahaney's theorem in an intro course?

    I'm not saying we should forget about it, I'm just saying that as more knowledge accumulates some things have got to go from an intro course.

  2. NP-completeness is the most important concept of all of theoretical computer science and Mahaney gives us a fundamental limitation on what these NP-complete sets can look like.

  3. The statement of Mahaney's theorem is to me as interesting as that of Ladner's theorem. The simplified proof above is nice and could be given as a guided exercise.

  4. Lance, I don't find your answer very satisfying.

    One can define all kinds of (random) properties about NP-complete sets, and spend the whole semester proving things about them. Why should anyone care about sparseness in particular? (If not b/c of the isomorphism conjecture.) Why would one think, a priori, that NP-complete sets could be sparse?

    And what do you think is taught in courses (or books) that should be taken out to make room for Mahaney?

  5. Although sparsity is sometimes not terribly well-motivated, it is definitely not a "random" property.

    1. NE = E is *equivalent* to all sparse NP sets being contained in P. (This is a result of Hartmanis, Immerman, and Sewelson.) So questions about sparse NP sets are strongly related to questions about NEXP.

    2. NP has polynomial size circuits iff NP is polytime Turing-reducible to a sparse set, i.e., NP is in P^{S} for a sparse S. So questions about reducibility to sparse sets are related to questions about polynomial size circuits.

    But I still am not sure I would teach Mahaney's theorem :)

  6. Locally in Buffalo, the question of extending Mahaney's Theorem to classes within NC---"how low can it go?"---such as in this paper led to further consideration of other properties of these low-level classes.

    Moreover, "sparse" got generalized to other notions of "low information content".

    (Word verification first gave me "strat". I am not a pure Strat, but rather an Oxfordian semi-collaborationist.)

  7. I have a question, possibly dumb: you say (φ,w) is in B iff f(φ,w) is in A; but doesn't this assume a particular kind of reduction (Karp?), not a general reduction (Turing?)

  8. There is a simpler proof of Mahaney's theorem (not due to me) via the well known tree pruning technique:

    Let f be a reduction from SAT to the sparse set S.
    Given formula F.
    Let m = |F|^k bound the number of strings in S up to |f(F)|.

    Develop the standard self-reduction tree of F
    until we have formulas F_0, F_1, ..., F_{m+1}.
    We show that we can prune one of them.
    The invariant we want to maintain is:
    if F in SAT then one of the formulas we keep in the tree is in SAT.

    Consider the sequence of strings

    f(F_0 or F_1), f(F_0 or F_2), ..., f(F_0 or F_{m+1})

    - if they are pairwise different,
    then F_0 is not in SAT and we can prune F_0.
    - if 2 are equal, say f(F_0 or F_i) = f(F_0 or F_j),
    then we can prune F_i:
    if F_i is in SAT then also F_0 or F_j is in SAT.

    Now go on extending the tree on the remaining formulas and do pruning.

  9. I think there is a bug in the sentence

    "There are only m elements in A so w1 is not in A and a' cannot be between w0 and w1."

    There are infinitely-many elements in A. I think you meant that there are m elements in the set { z : z = f(\phi, w) and w is an assignment to \phi }.

  10. I added a sentence clarifying that the only w we look at are assignments.

    For Daveagp: Mahaney's theorem holds for NP-complete sets via Karp (many-one) reductions. We know the polynomial-time hierarchy collapses if there are sparse complete sets for Cook (aka Turing) reductions but the implication P = NP is unknown.

  11. I think the sentence "Case 2: All the zi are distinct. There are only m elements in A so w1 is not in A and a' cannot be between w0 and w1."
    should be corrected to "... so z1 is not in A..."?

  12. Thanks for the clarification!

  13. Thomas: The proof you presented was given as a guided exercise in a complexity theory course taught by Manindra Agrawala at IITK. Though I don't remember Manindra saying this was due to him, I vaguely remember Somenath Biswas crediting it to him.

  14. Thanks for that proof Lance! It's simpler than the one I used to teach; I will use this one from now on.
    (Indeed, I think one should teach the theorem.)

  15. Is there a converse to Mahaney's theorem?

    1. Lets state Mahaney carefully so we can look at the converse.

      IF there exists an A that is sparse and NPC then P=NP


      If P=NP then there is a set that is sparse and NP-complete.

      TRUE but not that interesting: if P=NP then ALL sets in P
      (except EMPTY and Sigma^*) are NP-complete, so there will be
      a sparse set (in fact, all sparse sets except EMPTY)
      that is NPC.