# How is it possible for a problem to be NP-Complete under polylog-time reductions?

I have no source for this, but I've heard people offhandedly mention problems that are NP Complete under polylog reductions (I think SAT was one of them).

This confuses me - it seems to me that this is a violation of the nondetermistic time hierarchy. If SAT (or whatever) can be solved in $NTIME(n^c)$ for some $c$, and any $NP$-problem can be reduced to SAT in $O(n^k)$ time for some fixed $k$, then it seems that we can solve any $NP$ problem in $O(n^{c+k})$ nondetermistic time -- obviously false.

So, it seems to me that SAT (or whatever) can only be NP-Complete under polytime reductions, and that for any polynomial, we can find a problem whose reduction to SAT takes more than that polynomial amount of time.

What am I missing?

-

Alright, I figured it out by digging up some old source material. It turns out that it means that each bit of the output is computable in polylog time. In other words, the language $\{<x, k> \, | \, \text{The } k^{th} \text{ bit of } R(x) \text { is a } 1\}$ is decidable in polylog time (and so only reads a polylog amount of input). It turns out that SAT is indeed NPC under these reductions. This must be non-standard notation. Thanks for your help! –  GMB Apr 28 at 21:29