Questions tagged [circuits]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
35 views

Will a computer fail sooner the more you use it? [closed]

Is a computer like a car in the sense that the more you use it the quicker it will break down? Assuming that we have a regular computer with SSD that is running 24/7 versus a computer that is run ...
4
votes
0answers
41 views

Problems that are easy on boolean formulas but become NP-hard on circuits?

Many problems that take a boolean circuit as input are NP hard to compute. Do we have examples of such problems that become polynomial time computable when only boolean formulas are allowed as input? ...
0
votes
1answer
36 views

Relevance of depth for $NP$-completeness of fan-in $2$ and fan-out $1$ modest depth circuits?

Let $\mathcal C$ be a circuit of $m=f(n)$ input wires where every input is taken in the set $\{x_1,x_1',\dots,x_n,x_n'\}$ where $x_n\in\{0,1\}$ and $x_n+x_n'=1$ holds (not all $x_i,x_i'$ necessarily ...
1
vote
1answer
80 views

Iterated multiplication of permutation matrices

Given $m$ matrices of size $n\times n$ each of which is promised to be a permutation is it in $\mathit{quasiAC}^0$ or $\mathit{AC}^0$ to multiply the permutations where $m=\mathit{poly}(n)$ $m=\...
2
votes
0answers
64 views

Prove lower bound on boolean circuit

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
1answer
18 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
1answer
23 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 ...
0
votes
0answers
17 views

Newbie 2s complement to binary circuits help

I'm creating a circuit with in3, in2, in1, and in0, and outputs F11-F0. The circuit has to take the input in 2s complement and output the number in binary with the sign. F11 represents the sign bit (...
1
vote
1answer
19 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
2answers
45 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
0answers
24 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
0answers
26 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
1answer
106 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
0answers
27 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
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 ...
1
vote
1answer
17 views

Functions with small support have small circuits

I have been trying to understand the use of circuit models for boolean functions, and came across this question, that I am trying to struggle to understand: Show that if a function $f\colon \{0,1\}^n→\...
0
votes
1answer
139 views

Is NP in NP/Poly?

The answer is yes, NP/poly is defined as the class of problems solvable in polynomial time by a non-deterministic Turing machine that has access to a polynomial-bounded advice function--the advice ...
-1
votes
1answer
19 views

single circuit simulating multiple Turing machines

You can simulate polynomial time Turing machines with polynomial size circuits, can you simulate multiple poly time TMs with a single poly size circuit?
0
votes
0answers
17 views

Simulation of circuits with circuits

From classical results of universal simulation of Turing machines there exists a Universal Turing machine simulating any Turing machine with time complexity 𝑇(𝑛) in time 𝑇(𝑛)log𝑇(𝑛). Is there is ...
1
vote
1answer
31 views

Hardness of boolean functions

For a boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$, $H_{avg}(f)$ is a function from $\mathbb{N}\longrightarrow \mathbb{N}$, termed as the average case hardness, if $\forall$ circuit $C_n$ of ...
1
vote
1answer
82 views

Connection between Pseudo random generators and hardness

For a boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$ $H_{avg}(f)$ is defined as the largest $S(n)$ s.t. for all circuit $C_n$ of size $S(n)$, $\Pr_{x\in U_n}[C_n(x)=f(x)]<1/2+1/S(n)$. Here $...
1
vote
1answer
73 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 ...
0
votes
0answers
77 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 ...
3
votes
0answers
48 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 ...
5
votes
1answer
55 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 ...
1
vote
2answers
56 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$. (...
1
vote
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. ...
0
votes
1answer
44 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 ...
0
votes
0answers
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-- ...
3
votes
1answer
66 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 ...
0
votes
1answer
36 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 ...
1
vote
1answer
57 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 ...
4
votes
1answer
51 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 ...
2
votes
1answer
73 views

Construct a Circuit computing all boolean functions over n bits

Let $ n∈N $ . Construct a circuit with $ C_n(x_1,\dots,x_n) $ with $ 2^{2^n} $ outputs $ y_1,\dots,y_{2^{2^n}} $ which computes all distinct boolean functions $ f_i:\{0,1\}^n→\{0,1\}$ such that $ ...
0
votes
1answer
33 views

Problem with understanding Multi-party security circuit for secure stable matching

I am reading the following paper: MPCircuits: Optimized Circuit Generation for Secure Multi-Party Computation Paper Link I have following question: We have two groups shown in the circuit. Why we ...
0
votes
1answer
25 views

How to prove quantum circuit identity in Qiskit?

I am working on a simple quantum circuit identity. I proved it on paper with the tensor product, but i'm having trouble showing that with qiskit. I know I need to measure them somehow but i don't know ...
1
vote
2answers
100 views

Proof that uniform circuit families can efficiently simulate a Turing Machine

Can someone explain (or provide a reference for) how to show that uniform circuit families can efficiently simulate Turing machines? I have only seen them discussed in terms of specific complexity ...
2
votes
0answers
190 views

Example of *small* non monotone circuit such that any equivalent monotone circuit has greater size?

A "general" 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 ...
2
votes
1answer
80 views

Is it assumed that lower bounds on the size of monotone circuits apply to general Boolean circuits too?

A "general" 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 ...
1
vote
0answers
91 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 ...
2
votes
1answer
66 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
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 ...
2
votes
0answers
58 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
52 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
48 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
29 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 ...
2
votes
0answers
85 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
42 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
26 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
66 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(...

1
2 3 4 5