How can i implement a DFS search in the Boolean circuit? ( The output should be to assign each node it's DFS value from a root node)
I assume the complexity should be exponential, because each move we don't know the next node to be it's consequent node).
But is there any justification to that? Can I do it better?
The above question is algorithmic, Because it's a preliminary stage to make the circuit obliviously...