6
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.