# Questions tagged [circuits]

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

231 questions
Filter by
Sorted by
Tagged with
40 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 ...
15 views

66 views

### Existence of boolean function with exponential average case hardness

Show that for every large enough $n$, there is a boolean function $f\colon \{0,1\}^n\longrightarrow\{0,1\}$, whose average case hardness is exponential. The question is taken from Arora Barak ...
68 views

### Prove that the number of circuits with bounded fan-in (of 2) of size $s$ is at most $s^{O(s)}$

Prove that the number of circuits with bounded fan-in (of 2) of size $s$ is at most $s^{O(s)}$. Give the best explicit bound you can get. I know that for a circuit of size $s$ in order to generate a ...
34 views

### Circuit complexity of hardest monotone function

Show there exists a monotone function $f\colon \{0,1\}^n \mapsto \{0,1\}$, such that the minimal size of a monotone circuit that computes $f$ is $\Omega(2^n / n^2)$. Use the fact that the number of ...
50 views

### Is there a polynomial sized arithmetic formula for iterated matrix multiplication?

I found an article on Catalytic space which describes how additional memory (which must be returned to it's arbitrary, initial state) can be useful for computation. There's also an expository follow ...
50 views

### Show that the OR of n variables cannot be expressed as a polynomial over Fp of degree less than n

Here is a question from Computational Complexity by Arora and Barak: Show that representing OR of $n$ variables $x_1,x_2,\dots,x_n$ exactly over a polynomial in $GF(q)$ requires degree exactly $n$. (...
24 views

### Why mod $p$ gates cannot be computed by $ACC^0[q]$ circuits, $p$ and $q$ prime

I am going through Computational Complexity by Arora and Barak, and there I came across the proof of why mod $p$ gates cannot be computed by $ACC^0[q]$ circuits, where $p$ and $q$ are distinct primes. ...
36 views

### For a logic gate to be universal, must it necessarily be able to perform duplication?

It is said that a gate that can simulate AND and NOT is universal and able to recreate any classical circuit. I was looking at some of the circuits simulated by NAND, and for some of them, we need to ...
12 views

### Question about numbering of internal nodes in circuit diagrams when one circuit element has more than 1 internal node

I have the following circuit diagram that I've added labels for the internal nodes to using outside sources. I understand what an internal node is, however what I'm confused about is-- for example-- ...
63 views

### Counting circuits with constraints

Please forgive me if this question is trivial, I couldn’t come up with an answer (nor finding one). In order to show that there are boolean functions $f : \{0,1\}^n \rightarrow \{0,1\}$ which can be ...
25 views

### What is the difference between SIZE(n^k) and P/poly?

What is the difference between $\text{SIZE}(n^k)$ and $\text{P}/\text{poly}$? For reference: $\text{SIZE}(n^k)$ is defined as the class of problems solvable with Boolean circuits (of fan-in two) with ...
49 views

### What can this circuit be useful for?

I have calculated the boolean functions for $r$ and $f$: $f = \overline{s_1} \cdot s_0 + s_1 \cdot \overline{s_0}$. $r = \overline{s_0 \cdot s_1 \cdot s_2 \cdot s_3}$. Do you have an idea what an ...
48 views

### Can the W hierarchy by defined by circuits having a satisfying assignment of weight at most k?

Traditionally, the $W$ hierarchy is defined around the problem of weighted circuit satisfiability. More precisely, the class $W[t]$ is defined as the closure under $\mathrm{fpt}$-reductions of the ...
53 views

22 views

### Simulating Boolean Circuit with RAM

Statement: Every $T(n)$ size bounded Boolean circuit family, could be simulated with $(T(n))^2$ time bounded Random Access Turing Machine (RAM). Could you please supply me with a reference to an ...
24 views

### Which gates are “pre computation” universal?

In the following, by “functions” I will mean 2 input 1 output Boolean logic functions (for conciseness). A function is called “universal” if by using it (sometimes multiple times, chained together), ...
229 views

### Nandgame--I am not sure I understand the Data Flip-Flop specifications

Nandgame (nandgame.com) has you solve puzzles of increasing complexity which culminate in constructing a simple CPU. You start at the level of nand gates, and build everything else up out of those. I'...
49 views

$\begin{array}{rrrr | rr } 0& 0 & 0 & 0 & 1 &1 &1 &1 &1 & 1&0 \\ 0& 0 & 0 & 1 & 0 &1 &1 &0 &0 & 0&0 \\ 0& 0 & 1 &... 1answer 50 views ### What does it mean when a dot appears in a logic gate other than the NOT gate? (in logic diagrams) For example, this gate: looks like an OR gate, except there's a dot to the right. The dot is reminiscent of the fact that there's a dot in the NOT gate, so I wonder if it has something to do with ... 1answer 155 views ### Addition, multiplication, and apostrophe used to represent boolean algebra expressions? I'm looking at a worksheet that expresses boolean logic expressions using multiplication, addition, and apostrophes; something I've never seen before. I can make a guess that the apostrophe is ... 0answers 110 views ### Perfect Halver Construction? A sorting network is a circuit-based approach to sorting, built out of CompareExchange gates, which compute the function: $$\mathsf{CompareExchange}(x,y) = (\min(x,y), \max(x,y))$$ The input to the ... 2answers 49 views ### How to show all false outputs in a circuit? I have 3 input variables and the output for all 8 possible combinations is 0 (false). When making a circuit, how would I show this using gates or no gates at all? Thanks! 1answer 70 views ### How does$\mathsf{NP} \subset \mathsf{P}/\mathsf{poly}$imply these two inclusions? In the proof of Theorem 1 in this paper by Chen, McKay, Murray, and Williams the authors assume$\mathsf{NP} \subset \mathsf{P}/\mathsf{poly}$and (in different parts of the proof) state this implies ... 1answer 58 views ### Number of circuits with at most$m$logic gates I'm working on the same exercise as described in this post: How to show that hard-to-compute Boolean functions exist? In the answer there I don't understand how the number of circuits with at most$...
Given a Collection of Turing Machines $T_1, T_2, T_3,...T_n$ where $T_1$ denotes that the Turing machine can only take in an input of size 1. Is there any difference in computational power to a family ...
In Cook's famous paper on $\mathsf{NC}$, he cites the following result: PROPOSITION 4.7 (Cook and Ruzzo, 1983). $\mathsf{AC}^k$ consists of those problems solvable by uniform unbounded fan-in ...