3 ms·
From the Introduction: We will introduce a so-called 'Multistage graph Simple Path' (MSP) problem and prove its NP-completeness. So what they claim to be
by pedrocr 13y ago
From the Introduction:
We will introduce a so-called 'Multistage graph Simple
Path' (MSP) problem and prove its NP-completeness.
So what they claim to be NP-complete is their new problem and not the algorithm as it should be. I'll still say this will turn out to not be real. I won't even try to follow their paper but it's not written in LaTeX so it can't be real math... :)
- ColinWright 13y agoThey claim to have a new problem (MSP) which is NP-Hard because HC reduces to it, and they claim to have a polynomial algorithm to solve MSP. That's all very reasonable. What's less reasonable is that all of the references bar one are to their own papers, and a paper from 2010 claims to have been presented at a conference, and to prove this result. It's not passing the sniff test, but I'll still see if the first few pages make sense.