I have no source for this, but I\'ve heard people offhandedly mention problems t
ID: 652167 • Letter: I
Question
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(nc) for some c, and any NP-problem can be reduced to SAT in O(nk) time for some fixed k, then it seems that we can solve any NP problem in O(nc+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?
Explanation / Answer
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.