Hamiltonian Cycle Problem is in P(arxiv.org)

https://arxiv.org/abs/2105.07608

3 comments

What'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.

thanatos5195 anni fa

"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 ...

HelloNurse5 anni fa

Short 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.

[deleted]5 anni fa