1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – GMB
    Apr 28, 2014 at 3:04
  • 1
    $\begingroup$ Polylog-time reductions don't make sense, since you don't even have enough time to read the input. $\endgroup$
    – Yuval Filmus
    Apr 28, 2014 at 3:12
  • 1
    $\begingroup$ 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! $\endgroup$
    – GMB
    Apr 28, 2014 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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