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?

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

1 Answer 1

Reset to default
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.

Improve this answer
$\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.