Let @math be a 3CNF formula with n variables and m clauses. A simple nonconstructive argument shows that when m is sufficiently large compared to n, most 3CNF formulas are not satisfiable. It is an open question whether there is an efficient refutation algorithm that for most such formulas proves that they are not satisfiable. A possible approach to refute a formula @math is: first, translate it into a graph @math using a generic reduction from 3-SAT to max-IS, then bound the maximum independent set of @math using the Lovasz @math function. If the @math function returns a value @math , this is a certificate for the unsatisfiability of @math . We show that for random formulas with @math clauses, the above approach fails, i.e. the @math function is likely to return a value of m.
@cite_14: Assuming that NP spl nsube spl cap sub spl epsi > 0 BPTIME(2 sup n spl epsi ), we show that graph min-bisection, densest subgraph and bipartite clique have no PTAS. We give a reduction from the minimum distance of code problem (MDC). Starting with an instance of MDC, we build a quasi-random PCP that suffices to prove the desired inapproximability results. In a quasi-random PCP, the query pattern of the verifier looks random in some precise sense. Among the several new techniques introduced, we give a way of certifying that a given polynomial belongs to a given subspace of polynomials. As is important for our purpose, the certificate itself happens to be another polynomial and it can be checked by reading a constant number of its values.
@cite_1: We investigate relations between average case complexity and the complexity of approximation. Our preliminary findings indicate that this is a research direction that leads to interesting insights. Under the assumption that refuting 3SAT is hard on average on a natural distribution, we derive hardness of approximation results for min bisection, dense k-subgraph, max bipartite clique and the 2-catalog segmentation problem. No NP-hardness of approximation results are currently known for these problems.
Further motivation for studying efficient refutability of random 3CNF formulas is given in @cite_1 . There it is shown that if there is no polynomial time refutation heuristic that works for most 3CNF formulas with @math clauses (where @math is an arbitrarily large constant) then certain combinatorial optimization problems (like minimum graph bisection, the dense @math -subgraph, and others) have no polynomial time approximation schemes. It is an open question whether it is NP-hard to approximate these problems arbitrarily well, though further evidence that these problems are indeed hard to approximate is given in @cite_14 .