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

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, AC⁰ 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