[Solved]: Are all NP-complete languages log-space reducible to each other?

ignougroup
Problem Detail: NP-complete languages are reducible to each other in polynomial time. Does this mean that they are also log-space reducible to each other? It seems as if this is true because in log-space, we can have polynomially many computations.

Asked By : Ryan

Answered By : Yuval Filmus

Wikipedia makes the following points:

  1. It is unknown whether all NP-complete languages are NP-complete also with respect to logspace reductions.
  2. However, “all known” NP-complete languages are NP-complete also with respect to logspace reductions.
  3. There are some hints that a weaker class of reductions, AC0 reductions, may result in a different notion of NP-completeness.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41427  Ask a Question  Download Related Notes/Documents