New answers tagged circuits
0
votes
"Succinct circuit representation" on Turing machines?
A circuit is not represented "on" a Turing machine, rather a representation of the circuit is provided as input. It is straightforward to represent a circuit as a bit-string. For instance, ...
D.W.♦
- 150k
0
votes
Representing classical circuits with quantum gates
No, it's obviously not equivalent, because computation on a quantum computer is not known to be equivalent to computation on a classical computer.
Also, it's not clear what you mean by a "quantum ...
D.W.♦
- 150k
0
votes
Acyclic boolean circuit (DAG)
If your circuit can contain registers (or some other form of memory or state) (e.g., sequential logic), then yes, you can. You store the value of all variables in the registers, and you build a ...
D.W.♦
- 150k
Top 50 recent answers are included
Related Tags
circuits × 279complexity-theory × 143
logic × 26
boolean-algebra × 24
digital-circuits × 16
lower-bounds × 14
complexity-classes × 13
quantum-computing × 12
algorithms × 11
turing-machines × 11
reference-request × 11
time-complexity × 9
computability × 9
reductions × 8
satisfiability × 8
polynomial-time × 8
computer-architecture × 7
space-complexity × 7
computation-models × 7
np-complete × 6
arithmetic × 6
sequential-circuit × 5
boolean-complexity × 5
graphs × 4
terminology × 4