7
$\begingroup$

The 3-SAT problem can be defined as follows:

3-SAT

Input: A 3-CNF formula $\phi$ of size $m$ with $n$ variables.

Question: Does there exist a variable assignment that satisfies $\phi$?

Consider the following parameterized problem that is a variantion of 3-SAT:

CVA: Compressed variable assignment problem

Input: A number $k$ and a 3-CNF formula $\phi$ of size $m$ with $n$ variables.

Question: Does there exist a circuit $C$ of size at most $k\log(n)$ that computes a variable assignment that satisfies $\phi$?

Note: By circuit size, I mean the number of bits in the circuit's binary encoding where the circuits have bounded fan-in.

Below I will share some questions and results about the CVA problem.

Question 1: Do you happen to have any references to this problem or know of any related variants of SAT?

Question 2: How quickly can we solve the CVA problem in terms of parameters $m$, $n$, and $k$?

The brute force approach for solving this problem is to enumerate all circuits of size $k\log(n)$ and compute their corresponding assignments. For each assignment, we check if it satisfies $\phi$. This should take roughly $m \cdot n^k \cdot k\log(n)$ time.

Question 3: What is the parameterized complexity of this problem? How does it relate to other parameterized problems, the $W$ hierarchy, and other complexity classes?

It's worth noticing that the CVA problem is harder than a variation of the minimum circuit size problem found here: Parameterized complexity of deciding if a string can be computed by circuits of size $k\log(n)$

In particular, given a number $k$ and a bit string $x$, we can build a trivial 1-SAT formula $\phi$ that is only satisfied by $x$. Then, $x$ can be computed by a circuit of size $k\log(n)$ if and only if $\phi$ has a satisfying assignment that can be computed by a circuit of size at most $k \log(n)$.

Question 4: Does looking at compressible satisfying assignments have any practical significance? Has anyone ever measured the compression ratio of satisfying assignments for a collection of SAT instances that have come up in practice?

$\endgroup$
  • $\begingroup$ I didn't clarify what I mean by a circuit computing a variable assignment. Assuming that the variables are ordered $v_1$, $v_2$, $v_3$, etc. We can use the ordering to encode a variable assignment by a bit string. Then, a circuit computing this bit string is what I meant by a circuit computing a variable assignment. See here for a definition of what it means for a circuit to compute a bit string: cstheory.stackexchange.com/questions/37734/… $\endgroup$ – Michael Wehar Apr 1 '17 at 17:13
  • $\begingroup$ I could be mistaken, but I think I recall that this paper might talk about witness compression so it might have some relevance: "Infeasibility of instance compression and succinct PCPs for NP" $\endgroup$ – Michael Wehar Apr 1 '17 at 20:52
  • 4
    $\begingroup$ Note that to encode a circuit of size $s$ you need $\Theta(s \log s)$ bits, in the usual interpretation of "circuit of size $s$". So it's not $n^k$ to search over all circuits of size $k \log n$, it's more like $n^{k \log log n}$ $\endgroup$ – Ryan Williams Apr 2 '17 at 3:34
  • $\begingroup$ @RyanWilliams Yes, thank you for bringing up that there are multiple notions of circuit size. By size, I mean the number of bits in a binary encoding of the circuit. This notion was referred to as "bit size" in the comments here: cstheory.stackexchange.com/questions/37734/… $\endgroup$ – Michael Wehar Apr 2 '17 at 5:57
  • 1
    $\begingroup$ If you have only (k*log(n))/(3*log(k*log(n)) gates, then each gate needs at most 2*log(k*log(n)) bits, so the circuit description will fit into k*log(n) bits. ​ ​ $\endgroup$ – user6973 Apr 2 '17 at 8:25

Your Answer

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

Browse other questions tagged or ask your own question.