Algorithm for testing satisfiable fraction of linear equations mod 2 - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T02:19:34Z http://mathoverflow.net/feeds/question/62890 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/62890/algorithm-for-testing-satisfiable-fraction-of-linear-equations-mod-2 Algorithm for testing satisfiable fraction of linear equations mod 2 andy 2011-04-25T04:48:48Z 2011-04-25T04:48:48Z <p>Hello </p> <p>Let $F_{n,p}$ be a random process which generates a system of linear equations over $F_2$. The variables are ${x_1, ..., x_n}$ and for each of the $\binom{n}{2}$ $i,j$ pairs, the equation $x_i + x_j = b_{ij}$ gets generated with probability p, where $b_{ij}$ is chosen uniformly at random in $F_2$ too.</p> <p>let $\phi$ be such a system of equations und let $OPT(\phi)$ denote the maximal fraction of satisfiable equations.</p> <p>Given a constant $0 &lt; \epsilon &lt; 10^{-4}$</p> <p>I would like to come up with a deterministic polytime algorithm A, and a constant $c > 0$ such that A: </p> <p>accepts, if $OPT(\phi ) >= 1-\epsilon$ <br> rejects with high probability, if $\phi \in F_{n, c/n }$ </p> <p>My problem is that the algorithm is not allowed to (wrongly) reject any $1-\epsilon$ satisfiable $\phi$.</p> <p>My observation is that some subformula is unsatisfiable if, the subformula forms a cycle (when formulated as a graph) and a odd number of $b_{ij}$ equals 0.</p> <p>But i have no idea how to chose the c.</p>