Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

What you probably heard was that many problems are NP-complete under logspace reductions, for example 3SAT. All this means is that (say) the algorithm in Cook's theorem can be carried out in logarithmic space, and that many reductions among problems can be carried out in logarithmic space. Wikipedia contains a relevant discussion of various notions of reducibility and their relation to NP-completeness.

share|cite|improve this answer
I'm pretty sure it was polylogtime, but if there's nothing wrong with my logic then I'm sure I misunderstood some other subtlety. Thanks for answering so many of my questions on this site! You rock. – GMB Apr 28 '14 at 3:04
Polylog-time reductions don't make sense, since you don't even have enough time to read the input. – Yuval Filmus Apr 28 '14 at 3:12
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 '14 at 21:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.