5

If $\mathsf{NP} \subseteq \mathsf{P}/\mathsf{poly}$, then $\mathsf{SAT} \in \mathsf{SIZE}[O(n^k)]$ for some fixed constant $k$. The claimed results should follow by using this circuit to replace the $\mathsf{NP}$ oracle(s) involved in the relevant classes. For example, (2) follows by noting that $\mathsf{ZPP}^{\mathsf{NP}} = \mathsf{ZPP}^{\mathsf{SAT}}$ and ...


4

Usually $+$ means $\lor$, "multiplication" means $\land$, and $'$ means $\lnot$.


3

Let $1000 \leq s \leq 2^n/n$. Every function on $m$ bits can be computed by a circuit of size $O(2^m/m)$ (I believe that even the optimal constant is known). Choose a value of $m$ such that every function on $m$ bits can be computed by a circuit of size $s$, and furthermore $s = \Omega(2^m/m)$. Since there are $2^{2^m} = s^{\Omega(s)}$ different functions on ...


2

No, but something similar holds true. There is sort of a duality between even and odd levels of the W hierarchy. In particular, maximization problems like p-IndependentSet tend to inhabit the odd levels while minimization problems like p-DominatingSet inhabit the even levels. Asking for something of weight $\leq k$ is a minimization problem. In terms of p-...


2

You can check whether the unitary matrices are equivalent. def circuits_equivalent(a, b): au = Operator(a) bu = Operator(b) return au.dim == bu.dim and np.allclose(au.data, bu.data)


2

Éva Tardos gave a function which can be computed by a polynomial size general circuit but requires an exponential size monotone circuit. The circuit computes a good enough approximation to the Lovász theta function of the input graph. Razborov gave an $n^{\Omega(\log n)}$ lower bound monotone circuits computing the bipartite perfect matching function, for ...


2

Your question is solved by Patel, Markov and Hayes in their paper Optimal synthesis of linear reversible circuits. They mention a simple $\Omega(n^2/\log n)$ lower bound for the worst-case $M$, obtained by counting, and show that it is tight, in the sense that there is an $O(n^2/\log n)$ algorithm for any reversible $M$.


2

This is a NOR gate. You can implement a NOR gate using a combination of a OR and a NOT gate. However, in MOSFET implementation or other technologies (i.e. electrical hardware architecture), we can build a NOR gate directly and more efficiently (i.e. more efficient than using a OR and a NOT gate). That's why we use NOR as well.


2

I would recommend reading the Circuit Complexity lecture notes by Jonathan Katz, in which he discusses the problem clearly. You start off on the right foot. For two-input, single-output gates, there are 16 different possible logical functions. Each of the two gate inputs can either be from another of the $m$ gates or from one of the $n$ inputs, which leaves ...


1

In order to bound the number of functions computed by circuits of size $k$, you have at least two options: Construct a large number of circuits of size $k$, which by construction compute different functions. Consider a natural probability distribution on circuits of size $k$, and estimate the probability that two random circuits compute the same function. ...


1

SIZE($n^2$) consists only of problems that can be solved by circuit families of size at most $O(n^2)$. P/poly contains problems that can be solved by circuit families of size at most $O(n^3)$, and those solved by families of size at most $O(n^4)$, and so on. In particular, P/poly = $\cup_k$ SIZE($n^k$).


1

Good Question. It looks like some kind of ripple counter. It repeats after 15 steps. Values (consider the outputs to be 8,4,2,1) as 8,4,2,9,12,6,11,5,10,13,14,15,7,3,1. Zero only for one step after reset, not repeated.


1

Yes, that's correct. See the Tseitin transform, which describes how. It doesn't matter how the circuit $C$ was constructed.


1

What's wrong with A AND (NOT B)?


1

What you describe is essentially Turing machines with advice, the advice for length $i$ being simply the description of $T_i$. It is a classic result that the two models are equivalent in the case of poly-time TMs and poly-sized circuits, that is, both produce the same class $\mathsf{P}/\mathrm{poly}$. If the description length of $T_i$ is allowed to be ...


Only top voted, non community-wiki answers of a minimum length are eligible