2
$\begingroup$

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?

$\endgroup$
10
  • $\begingroup$ Have you tried reducing SAT to your problem? $\endgroup$ May 4, 2019 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$ May 4, 2019 at 21:42
  • $\begingroup$ On the other hand, is it NP-complete? $\endgroup$ May 4, 2019 at 21:46
  • $\begingroup$ Well, is it in NP? Can you verify a solution? $\endgroup$ May 4, 2019 at 21:53
  • 3
    $\begingroup$ Now you can answer your own question. $\endgroup$ May 4, 2019 at 22:09

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.