3 ms·
I want to add another important aspect, the aspect of NP completeness. There is a bunch of problems considered "NP complete" and they are all related such that
by contradictioned 9y ago
I want to add another important aspect, the aspect of NP completeness. There is a bunch of problems considered "NP complete" and they are all related such that it is easy to translate one problem into another (easy as in "quickly").
This means, first: If P == NP, then all of these problems become easy, and second: if P == NP and we find an algorithm that solves only one of the NP complete problems quickly, then this algorithm can solve all algorithms quickly.
Reversely, if now this paper's proof is correct so P != NP, then there is no algorithm that solves any of these problems quickly.
- dom0 9y agoNP completeness kinda works around the uncertainty of PxNP (with x ∈ {⊆, ⊊}), because it defines some sort of "weak subset" of NP comprised of "pretty sure these problems are not in P[, because no one yet thought of a polynomial reduction to a problem in P]". The last part in brackets is the catch here; if we could show that it is not possible, then P!=NP would immediately follow, and NP completeness would become a largely pointless exercise.
- slaymaker1907 9y agoNP completeness would still be of interest for particular algorithms because it would prove that those problems could not be solved in polynomial time. For instance, if factoring was shown to be NP complete, that would be a really useful result both for showing the security of algorithms like RSA as well as potentially disproving the extended Church-Turing thesis if quantum computers can be created.
- deleted 9y ago[deleted]