New answers tagged

1

A comparator circuit is a circuit computing a function on $x_1,\ldots,x_n \in \{0,1\}^n$. The inputs to the circuit are labeled with either constants ($0$ or $1$), inputs ($x_1,\ldots,x_n$) or negated inputs ($\lnot x_1,\ldots,\lnot x_n$). The only allowed gate is a comparator gate, which has two inputs $a,b$ and two outputs $a\land b,a\lor b$. The circuit ...


3

$\def\co{\mathrm{co}}\def\poly{\mathrm{poly}}\def\N{\mathbb N}$A language $L$ is in $(C/\poly)\cap(\co C/\poly)$ iff there are languages $$L_0\in C,\qquad L_1\in\co C,$$ and sequences of advice strings $\{a_{0,n}:n\in\N\}$, $\{a_{1,n}:n\in\N\}$ such that $$|a_{0,n}|,|a_{1,n}|=n^{O(1)},$$ and for any $n\in\N$ and $w\in\{0,1\}^n$, $$w\in L\iff(w,a_{0,n})\in ...


Top 50 recent answers are included