Definition
Correct Many-One Reduction
A many-one reduction
between problems and is correct if it preserves the answer to the problem instance. That means:
In other words,
and are equivalent as problem instances.
Correct Many-One Reduction
A many-one reduction
between problems and is correct if it preserves the answer to the problem instance. That means:
In other words,
and are equivalent as problem instances.