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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Wikipedia makes the following points:
It is unknown whether all NP-complete languages are NP-complete also with respect to logspace reductions.
However, "all known" NP-complete languages are NP-complete also with respect to logspace reductions.
There are some hints that a weaker class of reductions, AC0 reductions, may result in a different notion of NP-completeness.
answered Apr 15, 2015 at 19:57