Hamiltonian Cycle Problem is in P

by ototot • 5 years ago

6 3 5 years 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• 5 years ago

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.

tsukikage• 5 years ago

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.

Hamiltonian Cycle Problem is in P

Related Stories