
PreviousNext
We show that polynomially rankable distributions
do not provide harder instances than uniform distributions
for NP problems. In particular, we show that if Levin's
randomized tiling problem is solvable in polynomial time on
average, then every NP problem under any p-rankable
...
more >>>
We consider the threshold circuit complexity of computing
the multiple product modulo m in threshold circuits.
PreviousNext