New answers tagged

3

One notion that seems stricter in principle is that of "O(1)-local reductions", in that each output bit of the reduction only depends on O(1) bits of the input (as well as using logtime uniformity, I believe). See for example https://www.ccs.neu.edu/home/viola/papers/explicit.pdf


Top 50 recent answers are included