Snowblowing is NP-complete | Hacker News Reader

Snowblowing is NP-complete

punkrockor.wordpress.com

91 pointsjohndcook11 comments

Now I feel less bad about the vague suspicion that I was mowing my dad's lawn suboptimally for all those years.

Reminds me of Sokoban, which is NP-hard [1]

[1] http://en.wikipedia.org/wiki/Sokoban

I don't understand the reference to lawn-mowing being NP-complete - I thought I had a good algorithm: mow once around the outside, blowing grass inward, to get the edges without hitting things with the exhaust chute, then afterwards mow concentrically, blowing grass outward. Once the width is less than the turning radius of the mower, switch to only mowing along the long axis of the area.

Now, when there are rocks, stumps or trees within the area things get more interesting, depending on your tolerance for having to sharpen the blades...

Yards are generally not in shapes that look like mazes crossed with Hilbert space filling curves, which the problem statement permits.

Use a mulching/composting mower and don't worry about it.

What if you're raking wind rows... how does that affect the mowing problem? :)

I don't think the author understands what np complete actually means. I don't think that it is easy to verify that a snow Blown path is optimally efficient. It's interesting to discuss the complexity of day to day tasks, but optimal cleaning seems to be np hard, not np complete. You may think that you have the optimal solution until a friend of yours shows you his solution.

The author has a degree in operations research where matters of complexity theory pop up quite often. You are also welcome to read the paper and verify the claims of NP completeness instead of playing armchair critic.

Thanks, I spent ten minutes reading the post, clicking a lot of the underlined words that didn't result in links and missed that this was based on an academic paper.

The author uses NP-complete correctly. Section 2.2 of the paper establishes the problem is in NP and not merely NP-hard.

Your intuition about verifying optimal solutions has misled you here. Interesting optimization questions such as "shortest" or "best" are conventionally reformulated as decision questions about a particular bound. The verification then becomes easy: check to see, for instance, that the certificate path works and is shorter than the specified bound. A log-time search with such a verifier as a subroutine produces a polynomial verifier for the original optimality question.

Thanks for pointing out there was an attached paper!

It seems in section 2.2 the author points out that for a very special case of the snow blower problem, it is np complete ( see section 8 where they show a domain of polygons with holes). This special case might apply to snow blowing narrow paths through a field.

Right afterwards, the authors note that

> "the hardness of SBP in the fixed-throw model and in simple polygons is open. In fact, we do not even know what the optimal solutions are for simple cases like a square or rectangular domain."

which to me says that for the domain similar to an open field, or just a very wide pathway, the problem may be more complicated than NP-complete and they have not yet found an optimal solution for it.

Reply on news.ycombinator.com