3 ms·
Hamiltonian Cycle Problem is in P
- deleted 5y ago[deleted]
- thanatos519 5y ago"As a well-known problem in NPC, the Hamiltonian Cycle Problem can be now resolved practically in deterministic polynomial time, so this problem is in P and we prove that the conjecture of P=NP holds." I'm skeptical, but the paper is short ...
- HelloNurse 5y agoShort but messy. I suspect either that the algorithm doesn't actually work or that some worse than polynomial space or time cost hides in the numerous steps and subalgorithms.
- tsukikage 5y agoWhat's with the obsession with parallel computing? All the variations on "this bit is O(N^3) but if you have N computers working on it in parallel it's O(N^2)" - that's not how that notation works. Next step for the author is to represent the RSA challenge number factorizations as Hamiltonian graph problems. Once they've claimed the prizes, we'll know the paper is worth looking at.