Three-dimensional matching is NP-Hard
share
The standard proof of NP-Hardness of 3DM provides a power-4 reduction of 3SAT to 3DM. In this note, we provide a linear-time reduction. Under the exponential time hypothesis, this reduction improves the runtime lower bound from 2^o(√(m)) (under the standard reduction) to 2^o(m).
READ FULL TEXT