Comment by ColinWright | Hacker News Reader

Comment by ColinWright | Hacker News Reader

Just looking at the abstract:

    In this paper, we introduce a so-called Multistage graph Simple Path (MSP)
    problem and show that the Hamilton Circuit (HC) problem can be polynomially
    reducible to the MSP problem.

That would imply that the MSP is NP-hard. So far, so good.

    To solve the MSP problem, we propose a polynomial algorithm ...

That would imply that P=NP, and hence this would be a major result, with potentially wide-reaching consequences.

    ... and prove its NP-completeness.

Pause. This doesn't make sense. If you have a polynomial algorithm then it's in P. If you've reduced HC to MSP then you've already shown MSP is NP-Hard.

They use the word "its" - to what are they referring? The algorithm? That doesn't make sense, as an algorithm is not something that's NPC. The MSP problem? Earlier claimed results show that it's NP-Hard, now they're showing it's P, so to "prove its NP-completeness" doesn't fit.

However, English is not their first language (I assume) so perhaps I'm over-thinking irrelevant detail.

    Our result implies NP=P.

Yes, yes it would.

Now I'm off to see if I, as a non-specialist, can make any sense of it.

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... :)

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

Further into the article they state "This paper persents the full version of our idea to solve this famous problem. We will introduce a so-called 'Multistage graph Simple Path' (MSP) problem and prove its NP-completeness. To solve the MSP problem, we will propose a polynomial algorithm and prove its correctness."

> Pause. This doesn't make sense. If you have a polynomial algorithm then it's in P. If you've reduced HC to MSP then you've already shown MSP is NP-Hard.

This actually makes sense, although it wouldn't be necessary to point out.

If the author proves that P=NP, then all problems in P are NP-complete (because every problem in P is reducible to any non-trivial problem in P).

The paper doesn't look very promising to me, but the basic logic of the argument makes sense.

Reply on news.ycombinator.com