# Satisfiability Toward A Sequential Circuit

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?

• Have you tried reducing SAT to your problem? – Yuval Filmus May 4 '19 at 21:37
• 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)$. – Taylor Huang May 4 '19 at 21:42
• On the other hand, is it NP-complete? – Taylor Huang May 4 '19 at 21:46
• Well, is it in NP? Can you verify a solution? – Yuval Filmus May 4 '19 at 21:53
• Now you can answer your own question. – 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.