Loading ...
Sorry, an error occurred while loading the content.
 

[My Computational Complexity Web Log] Balanced NP Sets

Expand Messages
  • Lance Fortnow
    Last week I posed the following question: (1) Exhibit an NP-complete language L, such that for all lengths n1, L contains exactly half (2 n-1 ) of the strings
    Message 1 of 1 , Sep 11, 2003
      Last week I posed the following question:

      (1) Exhibit an NP-complete language L, such that for all lengths n≥1, L contains exactly half (2n-1) of the strings of length n.

      This question was posed by Ryan O'Donnell and solved by Boaz Barak. Here is a proof sketch.

      By using standard padding and encoding tools, (1) is equivalent to

      (2) There is an NP-complete language L and a polynomial-time computable function f such that for every n, there are exactly f(n) strings in L of length n.

      First we show how to achieve (2) if we replace "strings" with "total witnesses." Consider pair of formulas φ and ¬φ. The total number of satisfying assignments between them total 2n if the have n variables. We just create an encoding that puts φ and ¬φ at the same length. The total number of witnesses at that length is equal to 2n times the number of formula pairs encoded at that length.

      We now prove (2) by creating a language L that encodes the following at the same length for each φ

      1. φ, where φ is satisfiable.
      2. (φ,w) where w is a satisfying assignment for φ and there is another satisfying assignment u<w for φ.
      You can check that the language is NP-complete and the total number of strings in L for each φ is just the number of satisfying assignments of φ.

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 9/11/2003 09:06:21 AM

      Powered by Blogger Pro

    Your message has been successfully submitted and would be delivered to recipients shortly.