Questions tagged [circuits]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
36 views

Prove $\text{CorrectSuccintSolver} \in \mathbf{coNP}$

Define the following languages: $$ \text{SUCC-CVAL}=\{(S,x,i) : \substack{S \text{ is a succint representation for circuit } C \\ \text{ and } C_i(x)=1 \text{ where } C_i \text{ is the i'th gate in }...
0
votes
1answer
28 views

Algorithm to reduce a Circuit-SAT to NAND-SAT

I am trying to construct an algorithm to reduce OR, AND and NOT gates into NAND-SAT. Can someone give me a hint as to where to start?
1
vote
1answer
28 views

What class is the language $(C,(v_i)_{i=1}^m,x)$ complete to s.t. $C(x)$ is a boolean circuit with $m$ gates with values $\{v_i\}_{i=1}^m$

Given the following language: $$ L=\left\{\,(\,C,\,\{v_i\}_{i=1}^m, \,x\,) \enspace :\enspace \substack{C(x) \text{ is a boolean circuit with } m \text{ gates} \\i\text{'th gate value is } v_i \text{...
3
votes
1answer
30 views

Decidable languages unconditionally not in P/poly

What are some nice/natural examples of languages not contained in $P/\mathit{poly}$, preferably decidable ones? I'm interested in unconditional results rather than examples such as the Karp–Lipton ...
0
votes
1answer
25 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 ...
0
votes
0answers
23 views

Number of possible boolean functions in a DAG of lookup tables?

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 ...
2
votes
1answer
61 views

How does fan-out change circuit complexity?

Edit: Here's maybe a clearer presentation of my question. In a Boolean formula, all the gates have fan-out 1, and the graph representing the formula is a tree. In a Boolean circuit, the gates can have ...
0
votes
1answer
72 views

Details wanted on the reduction from Circuit Value to CFG Membership

Consider a Boolean Circuit $C$ which takes $n$ inputs and has one output. Notation: Let $\textit{size}(C)$ be the size of circuit $C$: the total number of gates in $C$. Let $G = (V,\Sigma,R,S)$ be a ...
0
votes
0answers
15 views

Mechanism of Howard's algorithm

How does Howard's algorithm avoids re-mapping of the non-critical nodes ?
2
votes
0answers
28 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 ...
1
vote
1answer
52 views

What is the comparator circuit?

The standard circuits $AC^i$, $NC^i$ are constructed using $AND$, $OR$ and $NOT$ of various fan-ins, fan-outs and depths. What is the comparator gate constituted from? Structurally why is it believed $...
0
votes
0answers
21 views

What is the depth of comparator circuit required in Gale Shapely and STCONN?

Stable matching problem and $STCONN$ can be solved using comparator circuits (refer https://arxiv.org/abs/1208.2721). What is the depth of the $CC$ circuit necessary for stable matching? Is it in $CC^...
2
votes
0answers
32 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 ...
3
votes
1answer
30 views

Is an AND gate which is noisy 1/3 of the time on only one of its inputs universal?

Imagine you have a noise-free NOT gate, and an AND gate with the usual truth table 00 0 01 0 10 0 (*) 11 1 but such that the case (*) is wrong 1/3 of the time, ...
1
vote
1answer
58 views

Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?

Let $C$ be an uniform complexity class for example $NL$ or $NP$. Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?
1
vote
1answer
36 views

Show that a circuit of size $s$ can be converted to a DeMorgan circuit computing the same function of size at most $2s$

I am trying to prove the above statement. A DeMorgan circuit is a circuit that has only $\{ \wedge, \vee, \neg \}$ gates, and the negation is applied only to input variables. So, assuming we have a ...
1
vote
1answer
26 views

How can you convert the depth of a boolean circuit to its size?

I know that the depth of a circuit is the maximal length from an input gate to the output gate of the circuit and its size is its number of gates. Is there a formula that you can go from depth to size ...
4
votes
0answers
44 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
41 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
102 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
69 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
30 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
27 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
21 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
20 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
60 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
38 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
28 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
107 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
28 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
21 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
168 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
23 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
19 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
37 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
83 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
80 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
83 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
61 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
72 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
57 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
63 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 ...
3
votes
1answer
71 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
59 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
60 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
52 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
80 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
39 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 ...

1
2 3 4 5 6