http://openproblemgarden.org/op/refuting_random_3sat_instances_on_o_n_clauses_weak_form Comments for "Refuting random 3SAT-instances on $O(n)$ clauses (weak form)" en http://openproblemgarden.org/op/refuting_random_3sat_instances_on_o_n_clauses_weak_form <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/feige_uriel">Feige</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/theoretical_computer_science">Theoretical Comp. Sci.</a> » <a href="/category/complexity">Complexity</a> » <a href="/category/hardness_of_approximation">Hardness of Approximation</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; For every rational <img class="teximage" src="/files/tex/9347bd4719a266c10e0c73946c70533f2b4266a2.png" alt="$ \epsilon &gt; 0 $" /> and every rational <img class="teximage" src="/files/tex/e3f8e135c571143e94f1d4f236326b862080b200.png" alt="$ \Delta $" />, there is no polynomial-time algorithm for the following problem.</p> <p>Given is a 3SAT (3CNF) formula <img class="teximage" src="/files/tex/271e416e5f903db9d5a872a172bff64213d15f88.png" alt="$ I $" /> on <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" /> variables, for some <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" />, and <img class="teximage" src="/files/tex/fa9a0d1b44e0ef76a5baadf58261ef02f7b7c079.png" alt="$ m = \floor{\Delta n} $" /> clauses drawn uniformly at random from the set of formulas on <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" /> variables. Return with probability at least 0.5 (over the instances) that <img class="teximage" src="/files/tex/271e416e5f903db9d5a872a172bff64213d15f88.png" alt="$ I $" /> is <i>typical</i> without returning <i>typical</i> for <i>any</i> instance with at least <img class="teximage" src="/files/tex/0051c86bd0f96850a6494aee0194b7e354f0fc1c.png" alt="$ (1 - \epsilon)m $" /> simultaneously satisfiable clauses. </div> </tr></td> </table> </td> </tr> </table> Feige, Uriel NP randomness in TCS satisfiability Theoretical Computer Science Complexity Hardness of Approximation http://openproblemgarden.org/op/refuting_random_3sat_instances_on_o_n_clauses_weak_form#comment Fri, 27 Feb 2009 01:03:21 +0100 cwenner 36884 at http://openproblemgarden.org