Questions tagged [circuits]

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

66 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
84 views

231 views

AC0 and first order logic equivalence

The page on descriptive complexity theory in Wikipedia states the following: "First-order logic defines the class FO, corresponding to AC0, the languages recognized by polynomial-size circuits of ...
29 views

What was the original paper that showed a simulation of turing machines via circuits?

It is a very standard construction in most complexity theory courses to turn a turing machine into a circuit. I thought this was due to Cook, but it looks like he did the reduction to SAT not through ...
33 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 ...
70 views

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 ...
29 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. ...
119 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 ...
16 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 ...
52 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 ...
54 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 ...
39 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 ...
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 ...
39 views

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?
96 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 ...
704 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 ...
170 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 ...
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.
49 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 ...
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 ...
129 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'...
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 ...
147 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 ...
247 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 ...
18 views

NC with nearest neighbor gates

Consider a circuit belonging to the class $\text{NC}^i$, as defined here. From my understanding, the circuit consists of AND, OR ar NOT gates, each of bounded fan in --- without loss of generality, ...
26 views

Make the forward counter go down

Suppose, I have a 4-bit binary Incrementor that uses XOR gates to increment the inputted number by the value of 1 (b0001, to be precise). Suppose, we connect it to 4 D-Flip-Flops (DFF) to create a ...
A K-input lookup table (K-LUT) can represent any function with K boolean inputs and a single boolean output. The number of possible functions represented by this LUT is $2^{2^K}$ according to this ...