2

A language $L$ is in $\mathsf{NP}$ if there exists a polynomial $p$ and a deterministic Turing machine $T$, running in polynomial time, such that: $x \in L$ if and only if there exists $y$ of length $p(|x|)$ such that $T(x,y) = 1$. Usually we assume that $|y| \leq p(|x|)$, but we can get this version using a simple padding argument, which slightly ...


2

In a trivial sense, no, because circuits have a fixed input size. To compute the same function as a Turing machine, you need an infinite family of circuits, one for each input size. So a single circuit can't even "simulate" one Turing machine. So let's restrict ourselves then to inputs just of size $n$, then the question is just are there two ...


2

In the average case, you want the circuit to succeed in computing the function for a large portion of all possible inputs. Since a constant function always succeeds for at least half the inputs (the majority of $f$), the interesting case in where you can achieve advantage which is greater than $\frac{1}{2}$. In the worst case, you want the circuit to succeed ...


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