New answers tagged circuit-complexity
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