3 ms·
They explicitly swept all the differences between different NP-complete problems under the rug as "some polynomial-time complexity", so I don't think he's worri
by andrewflnr 3y ago
They explicitly swept all the differences between different NP-complete problems under the rug as "some polynomial-time complexity", so I don't think he's worried about the translation between decision problems and others. He's trying to explain the broad significance of P vs NP for non-computer-scientists, so I'd agree that level of "subtlety" isn't necessary. Someone who cares and puts in the effort won't have a problem taking that in stride if they want to learn the full version later.