4 ms·
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 some
by wynand 17y ago
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.
- wynand 17y agoI 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.
- Groxx 17y agoExcept 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.
- deleted 17y ago[deleted]