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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.