patternMinor
Switching Lemma and AC0 reductions between SAT problems
Viewed 0 times
satswitchingreductionsac0betweenlemmaandproblems
Problem
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).
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).
Solution
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.
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.
Context
StackExchange Computer Science Q#41648, answer score: 8
Revisions (0)
No revisions yet.