4 ms·
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
by kcl 12y ago
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.
- snissn 12y agoThanks 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.
- deleted 12y ago[deleted]