Hacker News Reader

Comment by kaddar | Hacker News Reader

His claims about np-completeness implies that his research needs to be seriously questioned.

The quote was: "Computers and mathematics could also benefit. Maze navigation can fall into a class of problems known as NP-complete, "which computers have a surprisingly hard time solving, as the effort to solve them goes up exponentially with the scale of the problem," says chemist Irv Epstein of Brandeis University in Waltham, Massachusetts. "The kind of approach shown here with these mazes might be a very efficient approach to address this problem."

There are other cases of analog chemical processes beating out digital computations. But the reference to medicine also seems like a stretch - navigating a simple maze with a couple of acidic and basic chemicals seems very far away from a complex chemical hunting cancer in the human body.

Clearly, given varied acidic / basic areas in human bodies, this is not a "magic bullet" that'll only target cancer cells. They're also not claiming that this is the case (though the wording is quite vague).

At best, it'll increase the concentration of a drug in the cancer (among other places) above that of a "plain" drug, which is an improvement, thus should be investigated.

I don't see anything in the article that shows that he made the statement about NP-completeness. It seems that the quoted chemist made that statement.

For someone who's not a graph theorist, it's an easy mistake to make, since the longest path problem is, in general, NP-complete. He was probably just thinking of this problem.

I just downloaded his article, and he states that "With the advent of computers, algorithms for maze solving have become automated, but the solution times still scale unfavorably with maze size/complexity" and then references a paper by Dijkstra (Dijkstra, E. W. Numer. Math. 1959, 1, 269.).

That might be true for dense graphs, if you think that O(|V|^2 log|V|) is unfavourable.

A normal maze graph is planar and therefore |V| <= 3|E| - 6. Thus, maze problems can always be solved in O(|V| log|V|) time for a constant number of exits and starting points.

So, while the author made a little mathematical blunder ( single layer maze problems are efficient to solve), he's not the one that implied NP-completeness.

EDIT: Clarified my comment so that no-one can think I'm implying that an O(|V|^2 log|V|) algorithm is an NP problem.

Except that O(|V|^2 log|V|) is still polynomial.

(|V| > log|V|), therefore (|V|^2 |V| == |V|^3) > (|V|^2 log |V|). As a polynomial is a (loose) upper-bound, it cannot be greater than polynomial time, thus !NP-Complete.

Dijkstra's algorithm gives this as the worst-case performance (via http://en.wikipedia.org/wiki/Dijkstras_algorithm ), and finds shortest route from a root to all nodes, clearly including the exit:

  O( | E | + | V | log | V | )

Definitely not NP-Complete. Finding the distance from all nodes to all other nodes may be NP-Complete (not sure, but it seems like it would be, and doing so would be meaningless in a maze), but maze-solving is relatively easy in computing terms. Heck, even if you don't know the maze it's not NP-Complete: simply walk the whole thing and then calculate the shortest path.

Granted, the quote only says mazes can fall into NP-Complete... but I really don't know what you'd have to do to do that, without clearly falling out of a "maze" problem and into a more general "graph" problem.

The distance from all nodes to all other nodes is the Floyd-Warshall's All Shortest Paths algorithm, and it's V^3.

Cool, thanks! I've got more reading to do now :)

Reply on news.ycombinator.com