# Questions tagged [circuits]

A computation model in which the computation is described via circuits of various logic gates.

271 questions
Filter by
Sorted by
Tagged with
22 views

### Circuit Complexity of Permutation

We are here considering permutations of the form $F_2^n \mapsto F_2^n$. I am interested in the $AC^k[2]$ circuit complexity of such functions. What are the upper and lower bounds in this context? Does ...
1 vote
29 views

### Can Boolean circuits of polylog depth represent all Boolean functions?

Consider a Boolean circuit using (2-input) logical-and, (2-input) logical-or and logical-not as basic components. The depth of the Boolean circuit is the length of the longest path from the input to ...
• 258
202 views

### Shannon's result that some Boolean functions require exponential circuits

In 1949 Shannon proved, using a non-constructive counting argument, that some boolean functions have exponential circuit complexity, see [1] and many texts on computational complexity. This result has ...
• 8,178
1 vote
40 views

### prove that if $SAT\notin Size(2^{n/100})$ then CorrectSATSolver$\in P$

I need to prove that if $SAT\notin Size(2^{n/100})$ then CorrectSATSolver$\in P$. Where CorrectSATSolver $= \{C | C(\varphi) = 1 \iff \varphi$ is satisfiable$\}$. In other words, CorrectSATSolver ...
• 23
1 vote
22 views

• 2,824
23 views

• 17
72 views

• 248
1 vote
44 views

### Can you build a solver circuit from a verifier circuit?

Can you build a solver from a verifier? I see that if you start with an NP-verifier TM the answer is yes, you can build a solver TM. How about for circuits? Can you go from a circuit that implements a ...
1 vote
30 views

• 248