1
$\begingroup$

The Valiant-Varizani Theorem is given here. I also liked the description/proof given here - it's fairly straightforward.

I've read these works, and I'm still very shaky with constructing new hashed functions. I start with a 3-SAT function as a product of sums. My question is, for this given 3-SAT function, how do I construct a new function given that there are between $2^k$ and $2^{k+1}$ satisfying truth assignments?

I'd like to see this in great detail, because I plan on implementing this in a project that I'm working on.

MY PROGRESS

I'm thinking that I can just create some function with some new variables (I guess $k+2$ variables) that is true for only one value out of all possible truth assignments. Then, I combine this with the exclusive or of the old SAT function's variables, and this will give me a new function that is true roughly more than $1/8$ of the time.

  • 0
    @TsuyoshiIto: The algorithm in the lecture notes appears to calculate $h(x)=Ax+b$, where $A$ appears to be an $m \times n$ matrix and $b$ is an $m \times 1$ column matrix, with $A$ and $b$ randomly chosen. Is this correct so far? We can then compare the result to a _vector_, for lack of a better term, that is equivalent to all zeros or all ones (if we are working in binary). Is this also correct?2013-06-24

0 Answers 0