5
$\begingroup$

Say that a node of a circuit is small if it has fan-in at most 2 and large if it has fan-in greater than 2. The weft of a circuit is the maximum number large nodes in any path from an input node to an output node. Let $C_{t,d}$ be the class of circuits of weft at most $t$ and depth at most $d$.

The notion of weft is used fundamentally in parameterized complexity theory to define the W hierarchy. Namely, a parameterized problem P belongs to $W[t]$ if there is a parameterized reduction from P to $WCS[C_{t,d}]$ for some $d>1$, where $WCS[C_{t,d}]$ is the problem of determining whether a circuit in $C_{t,d}$ has a satisfying assignment of Hamming weigth exactly $k$.

I'm interested in circuits in which only OR gates are allowed to be large. More precisely, say that a circuit $C$ has OR-weft at most $t$ if the following conditions are satisfied.

  1. All negation gates are in the bottom layer.
  2. $C$ has weft at most $t$.
  3. All AND gates have fan-in $2$.

Let $D_{t,d}$ be the class of circuits of depth at most $d$ and OR-weft at most $t$. Say that a problem $P$ belongs to OR-$W[t]$ if there is a parameterized reduction from $P$ to $WCS[D_{t,d}]$ for some $d$.

Questions:

  1. Has some notion similar to the OR-Weft hierarchy been studied in parameterized complexity theory?

  2. What kind of functions can be computed by circuits of constant OR-weft?

$\endgroup$
2
$\begingroup$

First of all: your definition of $WCS[C_{t,d}]$ does not match the usual one. The common definition asks for a satisfying assignment of Hamming weight exactly $k$, rather than at most $k$, and this can make an important difference. However, regardless of whether you want at most, or exactly, Hamming weight $k$, the weighted circuit-sat problem for constant-depth circuits of constant OR-weft is polynomial-time computable. Here's why.

Consider a circuit of weft at most $c$, depth at most $d$, in which the negations are at the bottom and the AND-gates have constant fan-in. Starting at the bottom of the circuit, we will compute for each gate the set of minimal partial assignments that cause the gate to evaluate to true. By 'minimal partial satisfying assignment for gate g' I mean the following: a partial assignment of some input variables to true and false, so that any way of extending the partial assignment to a complete assignment satisfies gate $g$; and if any variable is removed from the partial assignment, then there is an extension that causes the gate to evaluate to false.

The main idea is that in the given type of circuit, for each gate we can give a polynomial-sized description of the set of its minimal satisfying assignments. By computing these bottom-up, we find a description of the minimal satisfying assignments of the output gate, from which we deduce the answer.

  • For a negation gate $g$ with input variable $x_i$, its only minimal satisfying assignment is $x_i \to 0$.
  • For an OR-gate $g$ with inputs $g_1, \ldots, g_m$, take the union of the sets of satisfying assignments for its input gates, and then prune the list to make it minimal. That is: if resulting union contains two partial assignments where one is a sub-assignment of the other (assigns values to a strict subset of the variables, and agrees with the other on values it gives to those variables) then remove the larger assignment from the list.
  • For an AND-gate $g$ with two inputs $g_1, g_2$, to satisfy it one needs to satisfy both $g_1$ and $g_2$. So for any combination of a minimal satisfying assignment for $g_1$ and a minimal satisfying assignment for $g_2$ such that these do not give any contradictory assignments, the combined assignment satisfies the AND-gate $g$. Compute all combined non-contradictory assignments by choosing a minimal satisfying assignment for $g_1$ and one for $g_2$, and then prune the resulting list to make it minimal as in the OR-case.

After computing the list of minimal satisfying partial assignments for the output gate, the answer to the weighted circuit sat problem can easily be read off. If there is a partial assignment that causes the output gate to be satisfied and that assigns values to at most $k$ variables, then there is a satisfying assignment of Hamming weight $k$; just set additional variables to true until reaching an assignment of weight exactly $k$. By the definition of partial satisfying assignment, this does not change the output gate's answer.

The main point is then to analyze the runtime of the procedure when applied to a circuit of depth $d$ with $n$ gates. The runtime depends on the sizes of the sets of partial assignments, i.e., the number of different minimal partial satisfying assignments for each gate. The minimal satisfying assignments for the input gates have size 1. The set for an OR-gate has size at most $n$ times the size of sets one level lower. The sets for an AND-gate have size at most quadratic in the size of the sets one level lower. So we get a recurrence.

Let $S(d)$ denote the maximum number of minimal partial satisfying assignments for a gate at depth $d$. Then $S(0) = 1$ and $S(d) \leq \max(n \cdot S(d-1), S(d-1)^2)$. It follows that $S(d) \leq n^{O(2^d)}$, so that for constant depth the sizes of the sets remains polynomial. Hence the algorithm runs in polynomial time.

$\endgroup$
  • 1
    $\begingroup$ I'm interested in the usual definition of $WCS[C_{t,d}]$, so I edited the question to "exactly k". $\endgroup$ – verifying Dec 22 '16 at 11:17
  • 1
    $\begingroup$ every function computed by circuits of constant depth can be computed in polynomial time, independently on the weft. I think what you meat in the end of your first paragraph is that $WCS[D_{t,d}]$ can be decided in polynomial time. I'm accepting the answer anyways. $\endgroup$ – verifying Dec 22 '16 at 11:20
  • $\begingroup$ You're right; I updated the first paragraph. $\endgroup$ – Bart Jansen Dec 22 '16 at 12:23

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.