patternMinor
Are all NP-complete languages log-space reducible to each other?
Viewed 0 times
spaceeachlogarelanguagesallreduciblecompleteother
Problem
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.
It seems as if this is true because in log-space, we can have polynomially many computations.
Solution
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.
-
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.
Context
StackExchange Computer Science Q#41427, answer score: 7
Revisions (0)
No revisions yet.