Questions tagged [circuits]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
43 views

Multiplication mod 2 without extra registers

For an arbitrary bitstring $(x_1, x_2,\ldots, x_n)$ and an $n\times n$ invertible binary matrix $M$ (fixed ahead of time), I would like to construct a circuit $C$ acting on these $n$ bits whose output ...
1
vote
0answers
10 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 ...
0
votes
0answers
18 views

Will learning about integrated circuits, help me be a better computer architect(long-term)? [closed]

I do not know if this is the right place to ask this type of question, but here I go, im thinking about learning integrated circuits as part of learning more about computer hardware in general (but ...
2
votes
0answers
35 views

Are minimum boolean circuit sizes for small problem sizes of an NP-complete problem known?

I think that a table with the following numeric values would be very interesting, but I could not find any table online displaying them: Choose any NP-complete problem (say, clique, but a problem ...
0
votes
0answers
51 views

How does this circuit work?

I saw a Computerphile video explaining how a simple circuit could store memory using some logic gates. However, I couldn't wrap my mind around how one could find the value of q if one needs not, ...
3
votes
1answer
26 views

Lower bound on number of (different) circuits of given size?

For circuits with $n$ input bits, we know that, for any function $s$, there are at most $O(s(n)^{s(n)}) = O(2^{s(n) \log s(n)})$ circuits with size at most $s(n)$. Say two circuits $C_1$ and $C_2$ ...
1
vote
1answer
21 views

Relationship between circuit size and formula size in Sipser text

The Sipser text (3rd edition) contains a proof that 3-SAT is NP-Complete based on Boolean circuits. Part of the proof contains the remark that the reduction from the circuit to the Boolean formula can ...
0
votes
0answers
9 views

Circuit : Switching function. Can I ignore RESET and CLOCK for the functions?

So if I have to state any function like state transition function or switching function can I ignore CLOCK and RESETS?
1
vote
0answers
82 views

Class of languages recognizable by n-bit formulas of size at most $T(n)$

A Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies: fan-in=2 for the AND and OR nodes fan-n=1 for the NOT nodes fan-...
2
votes
0answers
36 views

Circuit complexity of random Boolean functions

I just saw a YouTube video where Ryan Williams gives a talk about circuit complexity. He stated that random Boolean functions require exponential size circuits to compute, but I don't understand why ...
0
votes
1answer
23 views

Is this truth table possbile

I am trying to figure out if this truth table is possible. I've tried inverting the numbers, adding them, subtracting them, but I still cant find anything that works. I am starting to think that this ...
1
vote
1answer
43 views

What is $f(n)$ in $NTIME(n)\subseteq DTIME(f(n))$ if $CIRCUITSAT$ is in $P$?

If $CIRCUITSAT$ in $n$ variables and $m$ gates has an $O((nm)^c)$ algorithm for a fixed $c>0$ then $NTIME(n)\subseteq DTIME(O(f(n)))$ for large enough $f(n)$. What is the smallest $f(n)$ in $NTIME(...
0
votes
0answers
16 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 ...
0
votes
0answers
22 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), ...
1
vote
0answers
39 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'...
0
votes
1answer
26 views

Minimize circuit functions

$\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 &...
1
vote
1answer
26 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 ...
2
votes
1answer
54 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 ...
4
votes
0answers
92 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 ...
2
votes
2answers
35 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!
5
votes
1answer
63 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 ...
0
votes
0answers
30 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 $...
0
votes
1answer
21 views

What is the difference between a collection of Turing Machines and a family of Circuits?

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 ...
2
votes
0answers
38 views

Does Cook and Ruzzo's result also hold for logspace-uniform AC0?

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 ...
1
vote
1answer
29 views

Polysize bounded depth circuit for modified MAJORITY problem

I am trying to show the existence of a polynomial size, bounded depth monotone circuit on the inputs $(x_1,\ldots, x_n)$ that gives $1$ if $\sum x_i \geq n/2 + n/\log n$ and $0$ if $\sum x_i \leq n/2 -...
1
vote
1answer
28 views

How to show that the product of two binary numbers can be determined in AC1?

I was working on a proof to determine that a product cannot be done in AC0, how can a proof that can be done in AC1?
0
votes
0answers
24 views

Boolean circuit size of $i$th bit of determinant?

Berkowitz algorithm provides a polynomial size circuit with logarithmic depth for determinant of a square matrix using matrix powers. Is there a polynomial size boolean circuit for $i$th bit of ...
0
votes
0answers
19 views

Constucting QAP in the pinoccho paper

In this paper Pinocchio: Nearly Practical Verifiable Computation, on page 3 there is a way to construct the QAP and example doing it. Question : they say We pick an arbitrary root rg ∈ F for ...
1
vote
1answer
31 views

Logical characterization of $NC^1$

Morioka in his 2005 dissertation [1] referenced "On Uniformity within $NC^1$" by Barrington, Immerman, and Straubing. Using the following statement: Every $\mathbf{NC^1}$-predicate is computed by ...
1
vote
2answers
55 views

Why sum of two binary numbers cannot be determined in $NC^0$ but in $AC^0$?

Why sum of two binary numbers cannot be determined in $NC^0$ but it can be determined in $AC^0$?
0
votes
1answer
112 views

Turing machine and boolean circuits

As an example of languages that are in P/poly is the UHALT Problem : UHALT = { 1^n: n's binary expansion encodes a pair such that M halts on input x} We can create a boolean circuit of just AND ...
2
votes
1answer
26 views

Programs to circuit conversion

Suppose we have an algorithm for a decision problem with $n$ bit inputs that runs in $DTIME[f(n)]$ is there ways to convert to circuits of $O(f(n))$ size with AND, OR and NOT gates? How about when ...
2
votes
1answer
24 views

Satisfiability Toward A Sequential Circuit

Define a sequential circuit model be a directed graph with each vertices being a boolean gate. The difference is that we allow cycles in the boolean circuit. Each cycle will determine a boolean ...
2
votes
0answers
56 views

Implementing depth-3 circuit for XOR

In this set of notes, they claim that there is a size $O(2^{\sqrt n})$ depth-3 circuit (OR -AND -OR) that implements XOR. I tried for a little bit to figure out how to do this, but couldn't find ...
10
votes
1answer
843 views

Why isn't P and P/poly trivially the same?

The definition of P is a language that can be decided by a polynomial time algorithm. The definition of P/poly can be taken to mean a language that can be decided by a polynomial-size circuit (see ...
1
vote
2answers
379 views

Quantum NAND gate

Wondering how a quantum NAND gate would be implemented, and if it would be considered universal. I saw for quantum computing the Hadamard, phase, CNOT and π/8 gates are universal, but didn't see NAND ...
1
vote
2answers
93 views

If a NAND gate is universal, why you don't have NAND OISCs

If a NAND gate can be used to construct all other of the basic logic gates, then I'm wondering why you don't/can't have a purely NAND-based One Instruction Set Computer (OISC). All the OISC single ...
0
votes
2answers
54 views

How “add” could be implemented in only bitshift operations

Typically, add/subtract/multiply/divide are primitive operations in an Instruction Set Architecture (ISA). I am interested to know if they can instead be implemented efficiently using only bitshift ...
1
vote
0answers
35 views

Best-known Boolean Circuits for Clique? [closed]

Not having received a satisfactory response to this question in math.SE, I am asking it here: In this question, it is mentioned that the best known Boolean circuits for the Clique problem are non-...
0
votes
1answer
172 views

Simplifying SOP: implementing OR with NAND

I am learning how to implement basic logic gates using NAND. I have learnt that you can use De Morgan's theorem as such: $a+b = \bar{\bar a} + \bar{\bar b} = \overline{(\bar a *\bar b)}$ In other ...
1
vote
1answer
68 views

The role of depth of a circuit in its hardware implementation

The depth of a circuit is the maximal length of a path from an input gate to the output gate of the circuit [Reference] Question: What is the relation between the depth of a circuit and hardware ...
1
vote
1answer
27 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 ...
0
votes
0answers
42 views

Is the succinct version of P-complete problems out of P?

Consider the succinct versions of the P-complete problems as a Boolean circuit which represents its input in exponential more succinct ways. Could these succinct versions are in P or out of P?
3
votes
2answers
57 views

Weaker, but similar conditions to Turing completeness?

A model of computation is called Turing complete if it can simulate any Turing machine. This rules out for example a combinational logic circuit. However, there is a sense in which combinational ...
0
votes
0answers
19 views

Every circuit of size at most $S$ can be representd as a string of $9S \log S$ bits

I'm trying to understand this claim. I see that if there are $S$ vertices, then we can identify each vertex using $\log S$ bits. Now each vertex can be connected to, let's say, $S$ other ones (is ...
2
votes
0answers
57 views

Modular reduction in a finite field

Let $\mathbb{F}_p$ be a finite field of prime order $p$. Define $r_q : \mathbb{F}_p \to \mathbb{F}_p$ as $r_q (x) = x \bmod q$ with $q<p$. A tad more formally, treat $x$ as an integer in $[0, p)$ ...
2
votes
1answer
192 views

Circuits vs Turing Machines in the “nonuniform model of computation”

I just started learning about circuits in Chapter 6 of "Computational Complexity". There is an emphasis on the fact this model of computation allows different circuits for different input sizes of the ...
0
votes
1answer
28 views

What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?

What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?
1
vote
0answers
28 views

Introduction to circuit complexity? [closed]

The books I'm reading on complexity theory primarily are about complexity of decision problems by Turing machines. I'm interested in computational complexity of circuits, both boolean and continuous ...
0
votes
1answer
54 views

Boolean Algebra Simplifying complex equation

I am trying to simplify the following equation and I am getting stuck on a line and I can't cut it down any further. I'm not sure if certain 'moves' are legal or not. F(A,B,C,D) = A'B'C' +ACD + A’BCD ...

1
2 3 4 5