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 (2*^{n-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 2

^{n}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 2^{n}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 φ

- φ, where φ is satisfiable.
- (φ,w) where w is a satisfying assignment for φ and there is another satisfying assignment u<w for φ.

--

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

Powered by Blogger Pro