5 ms·
Yes, if a polynomial algorithm is found for a single NP-complete problem then any other NP problem can be converted and solved polynomially
by Almondsetat 3y ago
Yes, if a polynomial algorithm is found for a single NP-complete problem then any other NP problem can be converted and solved polynomially
- travisjungroth 3y agoI think this is what’s often missing when this topic is quickly presented. And, it makes the whole thing so much easier to understand. If someone were to prove P = NP by showing how to do it efficiently, that would make many computer problems easier to solve. Even problems like “guessing a password”, and that has obvious implications. If we just knew P = NP because a trusted oracle said so, or someone proved it without showing how to do the conversion, or the conversion was impossibly laborious (a constant 2*100 steps) then that changes much less. If someone proved P ≠ NP that would change the least, since that’s how we operate today. It’s not about getting the answer. It’s about what getting the answer suggests.
- dekhn 3y agoBut are you sure that woudl actually make any practical difference for any existing problems in the near term?