Define a sequential circuit model be a directed graph with each vertices being a boolean gate. The difference is that we allow cycles in the boolean circuit. Each cycle will determine a boolean equation.

For example, constructing a loop by connecting the input and output of a negation gate will yield the equation $x=\lnot x$, which is not satisfiable. Given such circuit, the "satisfiability" in the sense naturally occur. My question is:

Is determining whether this circuit can be satisfied known to be hard or easy? Furthermore, is finding or enumerating these configuration known to be hard or easy?

  • $\begingroup$ Have you tried reducing SAT to your problem? $\endgroup$ – Yuval Filmus May 4 '19 at 21:37
  • $\begingroup$ Oh indeed, I just find it to be NP-hard. Reduction is by adding a xor loop to examine the circuit. Namely, $y=y\otimes \lnot A(x)$. $\endgroup$ – Taylor Huang May 4 '19 at 21:42
  • $\begingroup$ On the other hand, is it NP-complete? $\endgroup$ – Taylor Huang May 4 '19 at 21:46
  • $\begingroup$ Well, is it in NP? Can you verify a solution? $\endgroup$ – Yuval Filmus May 4 '19 at 21:53
  • 3
    $\begingroup$ Now you can answer your own question. $\endgroup$ – Yuval Filmus May 4 '19 at 22:09

OK so now I figured this out. The problem is $NP$-complete. We could simply verify an assignment by checking each gate as an equation. For solving SAT of boolean function A(x), simply construct a equation, $y=y\otimes\lnot A(x)$ would suffice.


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.