<p>The 3-SAT problem can be defined as follows:</p>

<blockquote>
  <p><strong>3-SAT</strong></p>
  
  <p>Input: A 3-CNF formula $\phi$ of size $m$ with $n$ variables.</p>
  
  <p>Question: Does there exist a variable assignment that satisfies $\phi$?</p>
</blockquote>

<p>Consider the following parameterized problem that is a variantion of 3-SAT:</p>

<blockquote>
  <p><strong>CVA:</strong> Compressed variable assignment problem</p>
  
  <p>Input: A number $k$ and a 3-CNF formula $\phi$ of size $m$ with $n$ variables.</p>
  
  <p>Question: Does there exist a circuit $C$ of size at most $k\log(n)$ that computes a variable assignment that satisfies $\phi$?</p>
</blockquote>

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

<p>Below I will share some questions and results about the CVA problem.</p>

<p><strong>Question 1:</strong> Do you happen to have any references to this problem or know of any related variants of SAT?</p>

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

<blockquote>
  <p>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.</p>
</blockquote>

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

<blockquote>
  <p>It's worth noticing that the CVA problem is harder than a
  variation of the minimum circuit size problem found here:
  <a href="https://cstheory.stackexchange.com/questions/37734/parameterized-complexity-of-deciding-if-a-string-can-be-computed-by-circuits-of">Parameterized complexity of deciding if a string can be computed by circuits of size $k\log(n)$</a></p>
  
  <p>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)$.</p>
</blockquote>

<p><strong>Question 4:</strong> 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?</p>

CC BY-SA 3.0
2017-04-01T17:13:54.033Z
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: http://cstheory.stackexchange.com/questions/37734/parameterized-complexity-of-deciding-if-a-string-can-be-computed-by-circuits-of
Michael Wehar
CC BY-SA 3.0
2017-04-01T20:52:20.880Z
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"
Michael Wehar
CC BY-SA 3.0
2017-04-02T03:34:00.437Z
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}$
Ryan Williams
CC BY-SA 3.0
2017-04-02T05:57:26.323Z
@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: http://cstheory.stackexchange.com/questions/37734/parameterized-complexity-of-deciding-if-a-string-can-be-computed-by-circuits-of
Michael Wehar
CC BY-SA 3.0
2017-04-02T06:45:14.137Z
I removed the ETH hardness remark because I am no longer convinced that it is correct.  I will ponder this and follow up tomorrow.  :)
Michael Wehar
CC BY-SA 3.0
2017-04-02T13:45:53.000Z
@RickyDemer Thank you very much for the kind comment!!  Yes, if each gate has fanin two, then this makes sense.
Michael Wehar
CC BY-SA 3.0
2017-04-02T21:54:14.670Z
@D.W. Thank you very much for the kind comment!!  I'm sometimes confused about what is the best way to notationally represent parameterized problems and their fixed levels.  Let me explain.  Often a parameterized problem is a decision problem along with a function that represents a parameter.  This function takes in an input instance and outputs a number.  Sometimes I want to say 2-CVA where I am not referring to the parameterized problem, but rather to the decision problem expressed as a fixed level of the parameterized problem.  Alternatively, sometimes, I want to express...
Michael Wehar
CC BY-SA 3.0
2017-04-02T21:59:24.940Z
a decision problem along with a different function.  For example, I may informally write k^2-CVA to denote the compressed variable assignment problem along with a function that takes an instance, extracts the number k and squares it.  This informal notation that I used causes ambiguity because what if k were a variable representing a number.  Then, you may think I mean the decision problem (not parameterized problem) that is the fixed level k^2.
Michael Wehar
CC BY-SA 3.0
2017-04-02T22:08:20.370Z
@RickyDemer Thank you again for your comment as well.  I decided to edit the question to bounded fan-in circuits.  This allows for a more convenient and seemingly intuitive bit encoding where the encoding roughly consists of a list of gates where each gate has a type and a fixed size list of inputs or gates that feed into it.
Michael Wehar
CC BY-SA 3.0
2017-04-02T22:13:13.667Z
The alternative would be for each gate $g$ you have roughly log(n) bits where each of these bits is assigned to an input or gate and this bit represents whether or not that input or gate feeds into $g$.
Michael Wehar
CC BY-SA 3.0
2017-04-02T22:23:03.330Z
@D.W. Thank you again.  I really appreciate it!!  I editted the question to resolve this issue.
Michael Wehar
CC BY-SA 3.0
2017-04-08T05:25:44.227Z
Small comment: If we modify the problem so that the input is a Boolean formula (no restriction on it being 3-CNF), then I think we can show that the new problem is hard for every level of the W hierarchy.  If there is no progress on the 3-CNF case, then I might write this case up at some point.
Michael Wehar
CC BY-SA 4.0
2020-02-11T06:57:38.927Z
Thinking more about this, I suspect that the problem above is $M[1]$-hard (or hard in a similar way).  I say this, because I think we can reduce from 3-SAT on formulas with $k \log n$ variables and $n$ clauses to the problem above.
Michael Wehar
<cc.complexity-theory><circuit-complexity><sat><parameterized-complexity><fine-grained>
Given a Boolean formula, does there exist a small circuit that computes a satisfying assignment?
Michael Wehar
# Given a Boolean formula, does there exist a small circuit that computes a satisfying assignment?

(Asked by: username_0 on 2017-04-01)

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)$](https://cstheory.stackexchange.com/questions/37734/parameterized-complexity-of-deciding-if-a-string-can-be-computed-by-circuits-of)
>
> 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?

**Tags:** cc.complexity-theory, circuit-complexity, sat, parameterized-complexity, fine-grained
> **Comments:**
> **username_0**: 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: http://cstheory.stackexchange.com/questions/37734/parameterized-complexity-of-deciding-if-a-string-can-be-computed-by-circuits-of  
> **username_0**: 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"  
> **username_1**: 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}$  
> **username_0**: @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: http://cstheory.stackexchange.com/questions/37734/parameterized-complexity-of-deciding-if-a-string-can-be-computed-by-circuits-of  
> **username_0**: I removed the ETH hardness remark because I am no longer convinced that it is correct.  I will ponder this and follow up tomorrow.  :)  
> **username_0**: @RickyDemer Thank you very much for the kind comment!!  Yes, if each gate has fanin two, then this makes sense.  
> **username_0**: @D.W. Thank you very much for the kind comment!!  I'm sometimes confused about what is the best way to notationally represent parameterized problems and their fixed levels.  Let me explain.  Often a parameterized problem is a decision problem along with a function that represents a parameter.  This function takes in an input instance and outputs a number.  Sometimes I want to say 2-CVA where I am not referring to the parameterized problem, but rather to the decision problem expressed as a fixed level of the parameterized problem.  Alternatively, sometimes, I want to express...  
> **username_0**: a decision problem along with a different function.  For example, I may informally write k^2-CVA to denote the compressed variable assignment problem along with a function that takes an instance, extracts the number k and squares it.  This informal notation that I used causes ambiguity because what if k were a variable representing a number.  Then, you may think I mean the decision problem (not parameterized problem) that is the fixed level k^2.  
> **username_0**: @RickyDemer Thank you again for your comment as well.  I decided to edit the question to bounded fan-in circuits.  This allows for a more convenient and seemingly intuitive bit encoding where the encoding roughly consists of a list of gates where each gate has a type and a fixed size list of inputs or gates that feed into it.  
> **username_0**: The alternative would be for each gate $g$ you have roughly log(n) bits where each of these bits is assigned to an input or gate and this bit represents whether or not that input or gate feeds into $g$.  
> **username_0**: @D.W. Thank you again.  I really appreciate it!!  I editted the question to resolve this issue.  
> **username_0**: Small comment: If we modify the problem so that the input is a Boolean formula (no restriction on it being 3-CNF), then I think we can show that the new problem is hard for every level of the W hierarchy.  If there is no progress on the 3-CNF case, then I might write this case up at some point.  
> **username_0**: Thinking more about this, I suspect that the problem above is $M[1]$-hard (or hard in a similar way).  I say this, because I think we can reduce from 3-SAT on formulas with $k \log n$ variables and $n$ clauses to the problem above.  

---

## 0 answers

