# Questions tagged [circuits]

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

62 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0answers
83 views

0answers
26 views

### Comparing PRAM and Circuit Complexity, $NC^i$

I wondered about the following quote from NC (Wikipedia): $NC^i$ is the class of decision problems decidable by uniform boolean circuits with a polynomial number of gates of at most two inputs and ...
0answers
65 views

0answers
43 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 ...
0answers
28 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. ...
0answers
99 views

### Examples of relatively complex truth tables/logic gates in real life?

I'm researching truth tables, logical gates, and boolean algebra expressions. I'm trying to find specific real-life examples of logic gates and/or truth tables used in algorithm or circuit design in ...
0answers
15 views

### Boolean circuit multigraph

Let us say that our definition of a circuit is the one of a boolean circuit from [Vollmer]. He uses directed acyclic graphs to represent circuits where the computation nodes are labeled with some ...
2answers
664 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'...
1answer
43 views

### Smallest Circuit for Square of Sparse Symmetric Matrix

I have an n by n symmetric matrix, and I would like to compute its square in as small a circuit complexity as possible. It's sparse: there are sqrt(n) nonzero entries in each row/column, so the input ...
0answers
48 views

### Equality checking mod $10$ via arithmetic circuits

I'm interested in implementing equality checking mod 10 in an arithmetic circuit. Is this possible? Preliminary evidence points towards "no", but I thought it best to ask before completely writing it ...
0answers
36 views

### projection of arithmetic formulas to determinant

I am looking for a direct proof (i.e. without going through ABPs) that if $f(\bar{x})$ has an arithmetic formula of size $s$ then it is a projection of an $O(s)\times O(s)$ determinant. It seems ...
0answers
17 views

### What standardized formats (if any) exist for boolean circuits?

Being able to represent a Boolean circuit is useful in a number of areas of Computer Science, such as Circuit Satisfiability, Zero-Knowledge Proofs and Garbled Circuits. Are there any standards for ...
0answers
39 views

### About sign-rank of Boolean functions

Do we know of any necessary condition for a Boolean function or say a depth $2$ LTF circuit to have a low (~poly(dim)) sign-rank?
0answers
94 views

### How many bits we can negate using two/three NOT gates?

How many bits we can negate using two/three NOT gates ? I am newbie at this subject so I ask for help. It is about circuits. Edit After reading link given in comments by @D.W I think that I can ...
0answers
668 views

### 3 bit binary multiplier?

I have the following 2-bit binary multiplier How can I modify this 2-bit binary multiplier to make it a 3-bit binary multiplier? I notice that there are 2 half-adders, and there are a bunch of ANDs ...
0answers
167 views

### On power of $P/poly$

(1) We know that $EXP ⊄ P/poly ⇒ BPP$ is in $SUBEXP$. Does $SUBEXP ⊄ P/poly$ mean $P=BPP$ or anything close? (2) We know that if $NP$ is in $P/poly$ then $PH$ collapses to second level. What is the ...
0answers
27 views

### Arithmetic problems known to be in TC^{i+1} but not known to be in TC^i

Is there an arithmetic problem that is known to be in $TC^{i+1}$ but not known in $TC^i$ for any $i\geq0$? Concrete examples for $i=0$ would be of most utility however any arithmetic example is fine.
0answers
48 views

### Does an Expression in RPN Give us a Linear Way of Writing What Happens in a Circuit?

I mean, say we want to show how we can implement an OR gate in terms of a NAND gate. If we write in Polish notation, then we've suggested that the circuit takes the gates before the inputs. If we ...
0answers
58 views

### How do I triangularise a netlist?

I have a circuit that is represented as a netlist (specifically, an and-inverter graph). The desired outputs of this circuit are known. We can assume that some combination of the primary inputs will ...
0answers
122 views

### Simplifying circuits using boolean algebra

I am having a lot of trouble simplifying my circuit using boolean algebra. I am very new to this and any explanation would be greatly appreciated. I have y'+z+w'x+wx' I feel like I could use DeMorgan'...
0answers
41 views

### Is VHDL a description language for a Boolean circuit or are both concepts unrelated

I am looking for a way to translate basic c programs (subset of c or java or some declarative programming language) to a Boolean circuit. I know that Turing machines are reducible to Boolean circuits ...
0answers
146 views

### Functional Unit and Micro-operations Schematics

I'm sitting an exam on Computer Architecture in a few days and i'm stuck on a particular type of question. I'm asked to: Provide a detailed schematic for a functional unti that implements the ...
1answer
229 views

### Show that problem is PSPACE-complete - path in directed graph

I have a following problem: Given $n$ and graph of size $2^n$, and circuit with $2n$ input gates. Directed edge between $k$ and $l$ exists iff only and only we encode $k$ and $l$ as bits and launch ...
0answers
17 views

0answers
13 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-- ...