# 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$ 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 ...
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  and many texts on computational complexity. This result has ...
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 ...
1 vote
22 views

23 views

72 views

Given matrix $A \in \{0,1\}^{n \times m}$ with $n$ rows and $m = 2^n - 1$ columns. Where $j$-th column is binary decomposition of $j$ ($j = 1 \dots 2^n - 1$). For example, if $n = 3$: $A = \begin{... 1 vote 1 answer 46 views ### What is uniformity in Boolean circuits exactly? I have two questions on Kaveh's answer to Definition of uniform boolean circuit : Kaveh mentions that the input is in unary encoding. In the definition it says the input is$1^n$, afaik$1^n$is a ... 1 vote 1 answer 72 views ### How to find the reverse of a binary string with simple binary operators? I was wondering is it possible to create a simple circuit that detects if an input (a binary string) is a palindrome? So my approach is to feed the input to a circuit that reverses the input, ie if ... 1 vote 1 answer 31 views ### Circuits and Closure Under Reductions Suppose that$A$and$B$are languages such that$A\leq_P B$(many-to-one Karp reduction), and$B\in \mathbf{P/poly}$. How do we prove that$A\in\mathbf{P/poly}$? Using similar ideas like Cook-Levin (... 1 vote 2 answers 67 views ### Symmetric functions in NC¹ A boolean function$f \colon \{0,1\}^n \rightarrow \{0,1\}$is symmetric if$f(x)$depends only on the number of$1$s in$x$. It is known that every boolean function is in$\mathrm{NC}^1$, i.e. there ... 1 vote 0 answers 59 views ### Were boolean logic used in the analog computers? I began a simple collection of the events behind todays computers. My knowledege in these fields is so limited, and I read: "In the 1930s and working independently, American electronic engineer ... 2 votes 0 answers 30 views ### Generalizing Quantum Computation When you first learn more about computation you can imagine it in terms of boolean circuits. That is you get a boolean vector$v \in \lbrace 0,1\rbrace ^n$which you can then apply a circuit$C$to ... 2 votes 1 answer 109 views ### Closure properties of Alternating Circuit 1 level Recall that$\mathsf{AC^1}$is the class of circuits with unbounded fan-in, polynomial size, and logarithmic depth. Is this class closed under Kleene star? I thought it would be simple since it is ... 1 vote 0 answers 31 views ### Converse of Impagliazzo, Kabanets, Wigderson I am trying to prove that$\text{NEXP} = \text{MA} \Rightarrow \text{NEXP} \subseteq P/\text{Poly}$. I tried to approach the result via trying out the contrapositive, that$\text{NEXP} \nsubseteq P/\...
1 vote 