(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 φ.

## No comments:

## Post a Comment