1
$\begingroup$

In TCS, functions need to be converted into boolean circuits.

So is this Boolean circuit a combinational logic, i.e. a directed acyclic graph, satisfying the topological order?

I would appreciate your answer. Thanks!

$\endgroup$

2 Answers 2

2
$\begingroup$

A loop can be transformed into a circuit. The circuit might be bigger, but any polynomial-time program you can think of can be converted into a polynomial-size boolean circuit. Garbled circuits capture general two-party computation and is not limited to a restricted set of functions.

$\endgroup$
3
  • $\begingroup$ Yeah, that is more accurate. $\endgroup$ Mar 14 at 14:19
  • $\begingroup$ Hi! Can we compile these loop into cyclic combinational circuits? $\endgroup$
    – Emison Lu
    Mar 16 at 7:15
  • $\begingroup$ What is a cyclic combinational circuit? $\endgroup$ Mar 17 at 9:11
1
$\begingroup$

We have to think about the cost of realizing a specific kind of circuit complexity.

We can say that a general program executing some kind of interactive command can't be converted in a feasible circuit: think about a main() { while(true) {} }.

An interesting discussion can be read here Conditional Boolean circuits

$\endgroup$

Your Answer

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

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