Hot answers tagged

16

Addition and subtraction of binary numbers are in $\mathsf{AC^0}$. For any constant number $c$, $x \bmod c$ is $\mathsf{AC^0}$ reducible to division by $c$ ($\lfloor x/c \rfloor$): $$x \bmod c = x - (\overbrace{\lfloor x/c \rfloor + \cdots + \lfloor x/c \rfloor}^{c \text{ times}}) $$ It is known that $x \bmod c$ is hard for $\mathsf{AC^0}$ for any $c$ ...


10

$\def\ac{\mathrm{AC}^0}$Yes, $\ac\mathrm{PAD}=\mathrm{PPAD}$. (Here and below, I’m assuming $\ac$ is defined as a uniform class. Of course, with nonuniform $\ac$ we’d just get $\mathrm{PPAD/poly}$.) The basic idea is quite simple: $\ac$ can do one step of a Turing machine computation, hence we can simulate one polynomial-time computable edge by a ...


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