7
$\begingroup$

Have there been efforts to show (using the Switching Lemma), for example, that SAT or 3SAT cannot have an AC$^0$ reduction to 2SAT? What are the issues or difficulties involved?

SAT and 3SAT are complete for NP, and 2SAT is complete for NL under AC$^0$ reductions. Hence such a proof would separate NP from NL.

In the case of a 3SAT to 2SAT reduction in AC$^0$, the bottom fan-in is bounded by 3 (at least prior to the first switching).

$\endgroup$
  • 1
    $\begingroup$ very interesting! but not following exactly— wouldnt this also be nearly a P≠L proof? which is long open & considered very hard. there is some switching-lemma-like logic in monotone circuit lower bounds proofs initiated by Razborov & with many followup papers. encourage further discussion in theory salon chat $\endgroup$ – vzn Apr 21 '15 at 19:04
  • $\begingroup$ vzn, thanks.. It'd be a P $\neq$ L proof only if P=NP and L=NL.. Furthermore, showing the impossibility of an AC$^0$ reduction from HornSAT to 2SAT would separate P from NL (since HornSAT is complete for P under logspace reductions). $\endgroup$ – Martin Seymour Apr 21 '15 at 21:17
  • $\begingroup$ It's not true that the bottom fan-in is bounded by 3 in the case of 3SAT. The AC<sup>0</sup> reduction gets as input an encoding of the 3SAT formula (of a specific size). It can be an arbitrary circuit otherwise. Perhaps you're misinterpreting the switching lemma. $\endgroup$ – Yuval Filmus Apr 22 '15 at 2:26
  • $\begingroup$ Yuval -- ok, I get you now about the bottom fan-in. $\endgroup$ – Martin Seymour May 1 '15 at 6:02
8
$\begingroup$

It is hard to see how you would use the fact that the target of the reduction is 2SAT rather than, for example, 3SAT.

The common way one applies the switching lemma is roughly this. Apply a random restriction that fixes all but a $\lambda$ fraction of the inputs, for some small parameter $\lambda$ which depends on the parameters (size and depth) of the AC0 circuits in question. Then with constant probability, the function computed by the AC0 circuit becomes constant.

Applying this in our case, we have fixed all but $\lambda n$ of the inputs, and in return, some $\mu$ fraction of the outputs is fixed. And now what? We don't know anything about the reduction, so it's not clear how to obtain a contradiction. What's more, I don't see how you would use the fact that the target problem is 2SAT rather than, say, 3SAT, in which case there can be no contradiction.

The switching lemma is at its best when you have a concrete function in mind and you want to prove AC0 lower bounds for this specific function. Another, less typical, use of the switching lemma is to prove some general properties of any function computed by an AC0 circuit. The most famous example is Linial–Mansour–Nisan, which gives bounds on the rate of decay of the Fourier spectrum. It's not clear how you'd use information like this in your case.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yuval, you are absolutely right.. We are unable to use the fact that the target problem is 2SAT.. The target being 2SAT or 3SAT seems to make no difference.. Disappointing, but nothing much we can do, it appears. $\endgroup$ – Martin Seymour Apr 22 '15 at 2:54
2
$\begingroup$

some other angle/ pov on your question not taking it narrowly/ literally. a switching lemma-like construction has "coincidentally" been found to be at the heart of a celebrated/ very advanced proof in complexity theory showing an exponential lower bound required for a SAT-like problem in monotone circuits, initially discovered by Razborov, who won the Nevanlinna prize for this years ago. however his initial proof was not understood to be in that form and it took many years of reanalysis over multiple papers to bring out that connection. this effort is summarized in this paper: Monotone Complexity by Switching Lemma / Harnik, Raz. as cited in their paper its connected to a reformulation by Berg and Ulfberg [BeUl97].

so the switching lemma and reformulations of it continues to be an active area of research and a basic "device" in separating complexity classes, and therefore it probably would not be advisable to completely rule out its use in future (important? / significant?) separation results. also your question touches on P vs L which is open also and is thought by many to be possibly as hard as P vs NP (both questions have been open almost the same amount of time, roughly ~4½ decades). however, some limitations of the technique can be seen in the natural proofs barrier identified by Razborov/ Rudich.

as for 3SAT vs 2SAT as you inquire in your question, of course 2SAT is in P and 3SAT is NP complete, so any significant "reduction" would necessarily likely also relate P vs NP. wrt your NP vs NL idea, there are other active areas of research touching on the P vs NL question eg this recent analysis by Wehar, Hardness results for Intersection Non Emptiness

as for AC0 reductions and its implications for (open) complexity class separations, there are some connections noted in this recent breakthrough result, An average-case depth hierarchy theorem for Boolean circuits / Rossman, Servedio, Tan (eg p5)

Meyer's Question: Is there a relativized world within which the polynomial hierarchy is infinite?

... to answer Meyer’s question in the affirmative, it suffices to exhibit, for every constant d ∈ $\mathbb{N}$, a Boolean function Fd computable by a depth-d AC0 circuit such that any depth-(d − 1) circuit computing Fd requires super-quasipolynomial size.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.